[luatex] Strategy for creating a nodelist

[Hans Hagen]

On 9-3-2010 20:19, Taco Hoekwater wrote:
> Hans Hagen wrote:
>>> Looking at the documentation, node.insert_after() looks very much
>>> like what I want to use. But I don't quite understand its use when
>>> the head node is nil.
>
> Both for speed and for ease of use when building a moderate node list
> from scratch, the optimal solution is to only set the .next pointers
> and use a single node.slide() when the construction is finished: this
> is the fastest solution for any new list with non-trivial length, and
> it takes the least amount of code.
>
> When you have to splice one or two nodes into an existing node list,
> node.insert_before/insert_after are probably better.

in addition:

when these helpers were introduced we did some timing and the helpers 
are more efficient than similar code that used nil/next/prev/head 
checking and prev/next/head assignments

when deciding on an optimum, keep in mind that .next and .prev are in 
fact function calls (meta keys), so, node.insert_before is one call at 
the lua end while .next etc are each a call

in a similar fashion, when using node.traverse can be faster than a 
while loop, although in this case each iteration is a function call 
(luaish) so there

local n = head
while n do
    ...
    n = n.next
end

and

for n in node.traverse(head) do
   ...
end

are comparable; on the other hand, traverse_id can be faster as it does 
the comparison (save a call to n.id) and jumps over non matching nodes

when writing code one should keep in mind that in practice the 
difference in speed is not that large

Hans

-----------------------------------------------------------------
                                           Hans Hagen | PRAGMA ADE
               Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
      tel: 038 477 53 69 | fax: 038 477 53 74 | www.pragma-ade.com
                                              | www.pragma-pod.nl
-----------------------------------------------------------------