1.0.2.12: New hash-based implementation of ssets
authorJuho Snellman <jsnell@iki.fi>
Tue, 6 Feb 2007 04:48:36 +0000 (04:48 +0000)
committerJuho Snellman <jsnell@iki.fi>
Tue, 6 Feb 2007 04:48:36 +0000 (04:48 +0000)
commit2df8b5a0f18a3320d5b7652a958fae73cee1f937
treee318e39f6f020220e77a009ec494eaba1af50bba
parent1071bf1ca8292aeeef4a684d277f1e6b4693865a
1.0.2.12: New hash-based implementation of ssets

        * The old version that used sorted lists had bad worst case performance,
          which was especially noticeable with constraint propagation on
          hairy functions.
        * Use yet another custom hash implementation (with open addressing
          and double hashing), since the standard hash-tables are too heavy
          for this (e.g. locking overhead, memory consumption).
        * An sset implementation based on balanced trees was also tested,
          but in practice turned out to be even slower than the sorted lists,
          due to the high
        * DO-SSET-ELEMENTS no longer iterates in SSET-ELEMENT-NUMBER order,
          but we don't seem to rely on the old behaviour anywhere.
src/compiler/sset.lisp
version.lisp-expr