Re: Speed query

["Javier Guerra" <javier@...>]

On Tue, Mar 25, 2008 at 5:39 PM, David Given <dg@cowlark.com> wrote:
> Given that Lua is an interpreted language, conventional wisdom dictates
>  that it's most likely going to spend most of its time doing instruction
>  decodes rather than actual work. Therefore, the fewer the instructions
>  the better --- no matter what the instructions do.

you'd be surprised (as i am, often) to see how efficient a good VM is
(and Lua is one of the bestest's)

>  I want to implement a priority queue. I have two possible strategies
>  when inserting an item:
>
>  (a) binary chop through the array until I find the place to insert the
>  item, then call table.insert to do it.
>
>  (b) append the item at the end of the array and then use table.qsort to
>  sort the entire array.

(c) a heap queue: http://en.wikipedia.org/wiki/Heap_(data_structure)


>  (a) involves the least amount of theoretical work. (b) involves the
>  fewest number of actual instructions. So, which one is faster? And is
>  the answer still true when using LuaJit?

in most cases (b) is far faster than (a), not because of VM overhead,
but because sorts are so optimized.  just be sure to sort only when
needed and not after each insert.


-- 
Javier