[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
address@hidden