Speed Question -- Go, newLISP!!

[gcanyon]

In general, it seems newLISP is pretty fast, and intended to be so. I compared an implementation of my first solution in newLISP to an implementation of the same concept in Revolution, which I have used for several years. The code for each is included below.



The interesting point is that even though this is the very first code I wrote in newLISP, and I have many years' experience working with Revolution and environments like it, the newLISP code is roughly 7 times faster!! On my computer, running 10,000 iterations of the code takes about 2,300 milliseconds in newLISP, and about 18,000 milliseconds in Revolution.



By the way, I tried inlining the function call in the Revolution code, but that's not a significant bottleneck. Revolution doesn't have profiling tools (does newLISP?) so it's difficult to say just what's causing the slowdown. I have a reputation in the Revolution community for writing fairly fast code, but I'll post this to their mailing list to see if I'm missing something obvious.



Here's the newLISP code. If there's a way to make it faster, I'm happy to hear it.

Code Select Expand

(set 'start (time-of-day))
(seed (date-value))

#choose how many prisoners, and the measure of success
(set 'prisonerCount 100 'prisonerGoal 90)

(set 'wincount 0 'losecount 0)
(dotimes (t 100)

#set up random lists for the warden and the prisoners
(set 'warden (randomize (sequence 0 (- prisonerCount 1)))
      'prisoners (randomize (sequence 0 (- prisonerCount 1))))

#initialize an array that will store how the two lists map to each other
(set 'prisonerArray (array prisonerCount))

#populate the array with entries.
#the index is the number from the prisoners' list
#the value is the number from the warden's list
(map (fn (x y) (nth-set (prisonerArray x) y)) prisoners warden)

#initialize the results lists
(set 'loopList '() 'prisonerDoneList (array prisonerCount))

#for each prisoner entry
(dolist (i prisoners)

#if the prisoner has already been included in a list, go next
     (until (prisonerDoneList i)

#mark the prisoner as done
         (nth-set (prisonerDoneList i) 1)

#find what is in the prisoner's box,
#and start a list with the prisoner
(set 'x (prisonerArray i) 'oneLoop (list i))

#repeat until we find a loop
         (until (= x i)

#put the new box at the end of the list
                (push x oneLoop -1)

#mark the new prisoner/box as done
                (nth-set (prisonerDoneList x) 1)

#move on to the next box in the loop
                (set 'x (prisonerArray x)))

#when we have a complete loop,
#add it to the list of loops
         (push oneLoop loopList -1)))

#create a sorted list with the lengths of the loops
(set 'loopCount (sort (map length loopList) > ) )

(if (> (first loopCount) prisonerGoal)
    (inc 'losecount)
    (inc 'wincount)))
         
#print the results
(println "prisoners win: " wincount " and prisoners lose: " losecount " in " (- (time-of-day) start) " ms")





Here's the Revolution code. Sorry for the lack of comments. It follows much the same path as the newLISP code so it should be somewhat understandable.

Code Select Expand

on mouseUp
   local tPrisonersDone
   put 100 into tCount
   put ticks() into t
   repeat 100
     put randomList(1,tCount) into tWarden
     put randomList(1,tCount) into tPrisoners
     put empty into tResult
     put empty into tLoops
     repeat with i = 1 to tCount
       put line i of tWarden into tMap[line i of tPrisoners]
     end repeat
     delete local tPrisonersDone
     repeat with i = 1 to tCount
       if tPrisonersDone[i] = 1 then next repeat
       put i into x
       repeat
         put tMap[x] into y
         put 1 into tPrisonersDone[y]
         put y after tLoops
         if y is i then exit repeat
         put y into x
         put space after tLoops
       end repeat
       put cr after tLoops
     end repeat
     delete char -1 of tLoops
     repeat for each line L in tLoops
       put (the number of words of L) & " -- " & L & cr after tResult
     end repeat
     delete char -1 of tResult
     sort lines of tResult descending numeric by word 1 of each
     --put  cr & cr & tResult after fld "loops"
     if word 1 of tResult > 90 then add 1 to tFailed else add 1 to tSuccess
   end repeat
   put (ticks() - t) && "prisoners won" && tSuccess && "prisoners lost" && tFailed
end mouseUp

function randomList pStart,pStop
   repeat with i = pStart to pStop
     put i & cr after tList
   end repeat
   delete char -1 of tList
   sort lines of tList by random(100*pStop)
   return tList
end randomList


[cormullion]

I can't see any obvious ways to increase the speed of your code dramatically!



Although newLISP hasn't got much in the way of profiling, you can still have fun, because of newLISP's introspective nature. Try this for a laugh: put some of your code in a list:


 

Code Select Expand

(set 'some-code
'((set 's (sequence 0 (- prisonerCount 1)))
(set 'warden (randomize s) 'prisoners (randomize s))
(set 'prisonerArray (array prisonerCount))
(map n prisoners warden)
(set 'loopList '() 'prisonerDoneList (array prisonerCount))
(dolist (i prisoners)
(until (prisonerDoneList i)
(nth-set (prisonerDoneList i) 1)
      ...
      you get the idea

Then run the program from there:

Code Select Expand

(dotimes (t 100)
(dolist (piece-of-code some-code)
(println (time (eval piece-of-code)) " " piece-of-cade)))


So, you're reading lines of code from a list, then executing them, but timing the execution of each line, using 'time', and printing out the time and the code.



Sadly, the results aren't very enlightening, in this instance - 0 milliseconds isn't terribly helpful:

Code Select Expand


0 (set 's (sequence 0 (- prisonerCount 1)))
0 (set 'warden (randomize s) 'prisoners (randomize s))
0 (set 'prisonerArray (array prisonerCount))
...


Although I suppose you could always repeat each bit of code a few times:

Code Select Expand

(time (eval piece-of-code) 20)

which might amplify some small differences:

Code Select Expand

0 (set 's (sequence 0 (- prisonerCount 1)))
2 (set 'warden (randomize s) 'prisoners (randomize s))
0 (set 'prisonerArray (array prisonerCount))
3 (map n prisoners warden)

It looks hard to measure running programs without influencing them, though.



(Is this post rubbish? Perhaps I'm imagining things tonight)



I once got some useful ideas from this post: http://www.alh.net/newlisp/phpbb/viewtopic.php?p=5738">//http://www.alh.net/newlisp/phpbb/viewtopic.php?p=5738

[gcanyon]

After doing some research, a signiifcant portion of the difference came down to the arrays I used. Revolution uses associative arrays only. Even if you use x[1], x[2], x[3] etc., Revolution is still using associative arrays. Thus something simple like



                (set 'x (prisonerArray x)))



can be up to 9 times faster in newLISP. Interestingly, if prisonerArray is storing a single  character rather than a number, newLISP's performance is cut by a factor of 4 -- still faster than Revolution, but much slower than it is with an integer.



The interesting part to me was how similar newLISP and Revolution were at many tasks -- within 10% of each other for many commands. I'm no statistician but that seemed like a strange coincidence.