Maybe this is a noob question, but how do I return/get the results from the Multi Thread stuff then?
I have each thread finding vert positions, and its all good, and I can say print in each function and it works. But if I join those arrays to another one, and try to print at the end of processing, outside of the functions, it doesn’t work/ comes up as empty…
I sort of lost track of what the current leader was.
(
gc()
limit = 1000000
startM = heapfree
startT = timestamp()
a = #()
a[limit] = -1
a[1] = 1
for i = 2 to limit do
(
j = random 1 i
a[i] = a[j]
a[j] = i
)
format "Time: %s, Mem: %Kb
" ((timestamp()-startT)/1000.0) (((startM-heapfree) as integer)/1024)
format "Num unique elem %
" (a as bitarray).numberset
)
I’ve attached the algorithm written in C# so it can be fairly compared with the code contained in the encrypted mse.
And no, I didn’t peek into it first
The calling code I injected in looks like:
(
gc()
limit = 1000000
startM = heapfree
startT = timestamp()
a = randomIndexes limit
format "
Original code:
Time: %s, Mem: %Kb
" ((timestamp()-startT)/1000.0) (((startM-heapfree) as integer)/1024)
format "Num unique elem %
" (a as bitarray).numberset
)
(
gc()
limit = 1000000
startM = heapfree
startT = timestamp()
a = myrandomIndexes limit
format "
Biddle algorithm (thank you wikipedia):
Time: %s, Mem: %Kb
" ((timestamp()-startT)/1000.0) (((startM-heapfree) as integer)/1024)
format "Num unique elem %
" (a as bitarray).numberset
)
The output is:
CreateArrAssembly()
dotNetObject:MathOps.ArrayClass
randomIndexes()
myCreateArrAssembly()
dotNetObject:MathOps.myArrayClass
myRandomIndexes()
Original code:
Time: 1.242s, Mem: 27382Kb
Num unique elem 1000000
OK
Biddle algorithm (thank you wikipedia):
Time: 1.082s, Mem: 27382Kb
Num unique elem 1000000
[EDIT: I put some explicit locals in the calling function, I think I polluted my global namespace and it through the timing off. I re-uploaded the file]
[EDIT#2: I have a bug. The .NET random() has an exclusive upper bound.
so this:
source += ” j = list.Next(0,i);”
should really be:
source += ” j = list.Next(0,i+1);”
to give an unbiased result.
Sorry jonadb, yours still seems slower than the initial lo’s version and slower than my V5 (it’s lo’s version optimized)
(
print "V1 - lo"
gc()
start = timestamp()
seed(timestamp())
mem = heapfree
results = #{1..1000000} as array
for i = 1 to 1000000 do swap results[i] results[random 1 1000000]
end = timestamp()
format "processing: % seconds heap: %
" ((end - start) / 1000.0) (mem-heapfree)
)
(
print "V1 - jonadb"
gc()
start = timestamp()
mem = heapfree
p=0
n=1000000
results = for i = 1 to n collect i -- just generate a filler array
fn compareFN v1 v2=
(
ind=(random 2 n)
tmp=results[1] --always swap with index 1, doesnt matter, we have no index pointer here.
results[1]= results[ind]
results[ind]=tmp
--p=p+1
1 -- return 1 for the qsort function
)
dmy=#()
dmy[2000]=0 -- sorting an array with count=2000 results in 1002004 itterations of the shuffle loop, array empty so almost no memory use.
qsort dmy compareFN -- abuse the qsort function to just internally swap the array values
--print results -- uncomment en set n=10 to see if the algorithm works
end = timestamp()
format "processing: % seconds heap: %
" ((end - start) / 1000.0) (mem-heapfree)
--print p --uncomment this and the p=p+1 in the function to see the number of shuffles
)
(
print "V5"
gc()
start = timestamp()
seed(timestamp())
mem = heapfree
asize = 1000000
results = for i = 1 to asize collect i
for i = 1 to asize do
(
idx = random i asize
swap results[i] results[idx]
)
end = timestamp()
format "processing: % seconds heap: %
" ((end - start) / 1000.0) (mem-heapfree)
)
Results:
"V1 - lo"
processing: 1.49 seconds heap: 224075768L
OK
"V1 - jonadb"
processing: 1.769 seconds heap: 56065432L
OK
"V5"
processing: 1.413 seconds heap: 56065368L
OK
I didnt used the multithreaded version, because it’s obvious that any of this scripts multithreaded would be faster.
The “#{1…1000000} as array” code is obviously not useful, memory consumption is much higher. What you call V5 seems more useful.
jonadb’s latest code also skips some indices, though does not duplicate.
Biddle’s code seems very interesting.
I could fix the indices by enabling the --p=p+1 and use that as an index instead of the '1'..
I noticed my timings where way off, the first few runs (your code) max was increasing the heap on the fly, losing time.. the next runs (my code) were faster because the heap was big.. so in the end my code isn't faster indeed.. even slower :)
But more exiting news, The multithreaded approach by Kameleon inspired me to make this, not related to this challenge, but very useful.. it's a general for-loop multithreader.. read code-comments for details:
You call it like so:
multiloop 1 2000 8 "workerFunction" "CompleteEvent"
-- The above line reads like this: for i=1 to 2000 do ( workerFunction i), use 8 threads and call CompleteEvent() when done.
whole code:
--Multi threaded for-loop:
--
-- syntax equivalent: for i=<start> to <end> do ( <func> i ), spread over <cnt> threads and when completed call the function <comp>
--
-- Jonathan de blok - www.jdbgraphics.nl
-------------
fn multiloop start end cnt func comp=
(
cb="complete=0; fn callback a=( complete=complete+1 ; if (complete=="+(cnt as string)+") do ( "+comp+"(); ) )"
execute cb
end=end+1
chunk= (float end - float start)/cnt
st=start
end=chunk
complete=0
trs=#()
for i=1 to cnt do
(
trs[i]=dotnetobject "System.ComponentModel.BackGroundWorker"
n=i as string
run = "fn trfunc_"+n+" = ( for i="+(int st as string)+" to "+( int end as string)+" do ( "+func+" i "+n+"); );"
run=run+"dotNet.addEventHandler trs["+n+"] \"RunWorkerCompleted\" callback; "
run=run+"dotNet.addEventHandler trs["+n+"] \"DoWork\" trfunc_"+n
execute run
trs[i].RunWorkerAsync()
st=st+chunk
end=end+chunk
)
)
--This functions hold what would normally go into your for-loop's do( ) statement
fn workerFunction i t=
( --i= itterator, t=thread number
test_output=test_output + "i=" + (i as string) +"&t=" + (t as string)+" "
)
--This gets called when all thread have completed
fn CompleteEvent =
(
print "I'm done!"
)
-- do a test run:
test_output=""
multiloop 1 2000 8 "workerFunction" "CompleteEvent" -- for i=1 to 2000 do ( workerFunction i), use 8 threads and call CompleteEvent() when done.
print test_output
ha with this code running 12 threads:
processing: 0.096 seconds heap: 1535968L
edit: Damn, that was just measuring the creation of the threads, the script finishes while the threads keep running in de background… when putting the timing readout code in the ‘CompleteEvent2’ callback its back to 4 seconds again…
-- Multi threaded for-loop:
--
-- syntax equivalent: for i=<start> to <end> do ( <func> i ), spread over <cnt> threads and when completed call the function <comp>
--
-- Jonathan de blok - www.jdbgraphics.nl
-------------
gc()
start = timestamp()
seed(timestamp())
mem = heapfree
fn multiloop start end cnt func comp=
(
cb="complete=0; fn callback a=( complete=complete+1 ; if (complete=="+(cnt as string)+") do ( "+comp+"(); ) )"
execute cb
end=end+1
chunk= (float end- float start)/cnt*1.0
st=start
end=chunk
complete=0
trs=#()
for i=1 to cnt do
(
trs[i]=dotnetobject "System.ComponentModel.BackGroundWorker"
n=i as string
run = "fn trfunc_"+n+" = ( for i="+(int st as string)+" to "+( int end as string)+" do ( "+func+" i "+n+"); );"
run=run+"dotNet.addEventHandler trs["+n+"] \"RunWorkerCompleted\" callback; "
run=run+"dotNet.addEventHandler trs["+n+"] \"DoWork\" trfunc_"+n
execute run
trs[i].RunWorkerAsync()
st=st+chunk
end=end+chunk
)
)
nr=1000000
fn fillArray i t=
(
results[i]=i
)
fn shuffleArray i t=
(
ind=random 1 nr
tmp=results[ind]
results[ind]=results[i]
results[i]=tmp
)
--This gets called when all thread have completed
fn CompleteEvent =
(
multiloop 1 nr 12 "shuffleArray" "CompleteEvent2"
)
fn CompleteEvent2 =
(
print "done"
)
-- do a test run:
test_output=""
results=#()
multiloop 1 nr 12 "fillArray" "CompleteEvent" -- for i=1 to 2000 do ( workerFunction i), use 8 threads and call CompleteEvent() when done.
end = timestamp()
format "processing: % seconds heap: %
" ((end - start) / 1000.0) (mem-heapfree)
--print results
Great stuff jona, I was thinking about the same btw you can use sysInfo.cpucount to detect how many cores the cpu has.
Edit: This has just blown out my 3dsmax lol
A nice, will make an ‘auto’ option for the number of cores then
But the timing results aren’t accurate, see my edit in the above post. We’ve just measured the time it took to create the threads. The script finishes and the threads continue to work in the background.
Timing readout code should go in the ‘CompleteEvent2’ function… which results in somewhat longer timings
Check this out then, I’ve re-writen my multithreaded version and now it gives the accurate time to finish the loops.
(
print "V6"
gc()
startg = timestamp()
seed(timestamp())
mem = heapfree
asize = 1000000
results = for i = 1 to asize collect i
wthreads = 2
adiv = asize / wthreads
fn dowork1 =
(
for i = 1 to adiv do
(
idx = random i asize
swap results[i] results[idx]
)
wthreads=wthreads-1
)
fn dowork2 =
(
for i = adiv to asize do
(
idx = random i asize
swap results[i] results[idx]
)
wthreads=wthreads-1
)
fn workdone =
(
if wthreads == 0 then
(
endg = timestamp()
format "processing: % seconds heap: %
" ((endg - startg) / 1000.0) (mem-heapfree)
format "Num unique elem %
" (results as bitarray).numberset
)
)
MainThread = dotnetobject "System.ComponentModel.BackGroundWorker"
print "MainThread"
dotNet.addEventHandler MainThread "DoWork" dowork1
dotNet.addEventHandler MainThread "RunWorkerCompleted" workdone
--------------------
SecondaryThread = dotnetobject "System.ComponentModel.BackGroundWorker"
print "SecondaryThread"
dotNet.addEventHandler SecondaryThread "DoWork" dowork2
dotNet.addEventHandler SecondaryThread "RunWorkerCompleted" workdone
-----------------------
MainThread.RunWorkerAsync()
SecondaryThread.RunWorkerAsync()
)
Result:
"V6"
"MainThread"
"SecondaryThread"
undefined
processing: 0.999 seconds heap: 56077208L
Num unique elem 1000000