[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Axiom-developer] 20080216.01.wxh.patch (hash tables to speed compil

From: Waldek Hebisch
Subject: Re: [Axiom-developer] 20080216.01.wxh.patch (hash tables to speed compiles)
Date: Sat, 16 Feb 2008 23:01:18 +0100 (CET)

Tim Daly wrote:
> This code is a performance improvement by Waldek Hebisch.
> (Fricas patches 232 and 233).
> The essence of the speedup appears to be caused by two factors.
> The original code was non-recursive and used union across lists.
> The new code is recursive. It also uses a hashtable to reduce
> the amount of redundant list construction.

Two comments:

1) mkCategory/sigParams: the original code was recursive.  Gain
   comes from avoiding unions: with unions algorithm is quadratic
   (and may be worse because builtion Lisp union may be slow),
   new version builds list with duplicates in linear time.  The
   final loop used hash table to quickly remove duplicates.

2) The second patch (233) tries to avoid lookups in environment if
   it is clear that the lookup will fail.  The whole gain is in
   get1 function (but you did not include this hunk...).  The
   other parts are just to put correct info into the $envHashTable.

                              Waldek Hebisch

reply via email to

[Prev in Thread] Current Thread [Next in Thread]