Computer Science Canada Speed Differences |
Author: | Raknarg [ Tue Mar 13, 2012 8:31 pm ] | ||||
Post subject: | Speed Differences | ||||
I have these two algorithms for making bezier curves. If you test them both out, you'll notice that one is faster than the other:
I was wondering if someone could explain why that is. My guess would be because of the flexible arrays in the second one, lx and ly. |
Author: | Dreadnought [ Tue Mar 13, 2012 9:02 pm ] |
Post subject: | Re: Speed Differences |
Which one is supposed to be fastest? After I added a delay of 20 ms to the first program to match that of the second program I didn't see a noticeable difference. |
Author: | chrisbrown [ Tue Mar 13, 2012 9:53 pm ] |
Post subject: | RE:Speed Differences |
Resizing an array can be very costly. If the next location in memory after the end of the array is in use, it becomes necessary to copy the entire array somewhere else. As far as I can tell, there's no need for a flexible array at all. Why not just allocate from 0 .. upper (x) - 1? In general though, you want to minimize the number of enlargements you make. When memory consumption isn't a factor (as is usually the case), a large inflexible array with a size variable is usually a better choice. The only caveat is that it should be passed to functions with the var keyword in the parameter list to pass be reference instead of copying the whole thing. |
Author: | DemonWasp [ Tue Mar 13, 2012 10:19 pm ] |
Post subject: | Re: RE:Speed Differences |
chrisbrown @ Tue Mar 13, 2012 9:53 pm wrote: ...If the next location in memory after the end of the array is in use, it becomes necessary to copy the entire array somewhere else.
While that's technically correct, it would be more accurate to say "it is always necessary to allocate the new, larger array, copy all the elements over, and delete the old array". The reason has to do with how the OS allocates memory. There's (usually) no way to ask whether you can grow that particular segment, or allocate the next one over. If you DO have to write something that resizes arrays, try to make it so that it doubles the size of the array every time it needs to grow it. Then you'll have log(N) "resize" operations rather than N, which makes it a lot faster. |
Author: | chrisbrown [ Tue Mar 13, 2012 10:46 pm ] |
Post subject: | RE:Speed Differences |
Cool, good to know re: allocation. And no argument on doubling, but I'll just add that still necessitates a size variable, which might be overkill for small N. |
Author: | Raknarg [ Wed Mar 14, 2012 3:57 pm ] |
Post subject: | RE:Speed Differences |
The first one is supposed to be faster, I've tested it on two separate computers. It was a significant difference, too. |
Author: | Dreadnought [ Wed Mar 14, 2012 4:49 pm ] |
Post subject: | Re: Speed Differences |
Well the second program has a 20 ms delay in its loop, if I remove it the two programs seem to run at approximately the same speed. |
Author: | Raknarg [ Wed Mar 14, 2012 9:48 pm ] |
Post subject: | RE:Speed Differences |
oooh, i didnt see that -.-' thanks, I thought I had looked through it :/ Good thing for me, I dont think of such simple things as ctrl+f XD |