Proposal for a new hash interface

Proposal for a new hash interface

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 5588 bytes --]

High all,

I have taken the task to study a possible hash table implementation mostly
in scheme but still speedy. I am still experimenting with different
approaches. With managing code and iteration higher order functions in
scheme and lower order implemented in C. I can match current hash
implementations but with hash-fold and hash-for-each 10-20X faster and
better semantics as it is not going via C.

I suppose the implementation is more memory intensive than the current
implementation. But much much safer and featurefull.

So what are the features:
* goops based organisation

* allows one to type a hash table, e.g. disallow the use of
different versions
  of the assessors for the same hash.

* surprisingly fast although we define goops methods for the accessors

* A flag that indicates that (hash i) = i, for integers, which is used in
python

* Possible to freeze has hash e.g. it will not grow or shrink, when cleared
only
  all the values will be cleared.

* A possibility to use (hash x (ash 1 60)) as a key, e.g. when checking if
a slot
  is equal, we compare only the long hash.

* A proper separation between general code that can be pushed to C for
speed    and scheme for nice integration and power

Code:

scheme:
https://gitlab.com/tampe/guile-persist/-/blob/master/ice-9/hashish.scm

C:
https://gitlab.com/tampe/guile-persist/-/blob/master/src/hash/resize.c

C/Scheme integration
Each handle is of the form
(hash key val)

So when we store the key value pair we also store the hash values which are
60bit wide. This means that we can dispatch the search for an item using
only the hash value and many operations can be done in a general way that
can be pushed to C (if we want). So typically you first try to use C and
when it finds a match you need to do the final check in scheme using the
correct equal predicate. This means that we can achieve a very extensible
system that you can extend without losing much performance. These
primitives make the scheme code beautiful and well organized so we should
probably keep this semantic even if we decide to do everything in guile
scheme.

Example, consider that we have designed a new hash table semantics. The
easiest is to supply a hash function and a equal predicate like so

(use-modules (ice-9 hashish))
(use-modules (oop goops))

(define (myhash    k s) ...)
(define (myequal? x y) ...)

(define-class <my-hash-map> (<stis-hash-map>))
(stis-new-hash-type <my-hash-map> make-my-hash-table myhash myequal?
     my-hash-ref  my-hash-set!  my-hash-remove!)

Preferably when we do not need to know the type of the hashtable we can
either use the methods (slow) stis-hash-ref stis-hash-set! stis-hash-remove!

The fast way is to take advantage of the following construct,
(define H (make-my-hash-table))
(stis-with-hash-accessors (H : ref set remove)
    ...
    (set k1 (ref k2 #f))
    ...
    (remove k3)
    ...)

Both these methods are safe.

There are some extra tools available.

> stis-hash-resize!
One can resize a hashtable as one likes

> stis-hash-define-world!
One can fill the hash table and then specify that this is the world. Then
If all long hashes that are stored are unique, no equal method will be used
for identity and the hashmap will be freezed

> stis-hash-unworld-it
Unset the world property (not yet coded)

> stis-hash-copy
Create a new hashtable (this is not yet coded)

IMPLEMENTATION
The implementation is not yet defined, we need to test it and try
different versions. But One thing that one can notice are that by reducing
the
size if the hashtable one can speed up all operations. So the idea is to
store
a list of hash/index pairs in the hash and use varying sized cells for
this. The
smallest cell is 2 bytes and we can use more bytes for the index (size of
hash table) and fewer for the hash itself) this means that we could use a
size of 64 for the hash value and allow 1024 items in the hash table.
Similarly as the hash  grows we will use 32bit cells and split the maximal
size of the hashtable between the hash value and the hash table size. The
next size is 64bit cells and the last one are 128 bit cells. There will be
a fallback hash table which is the usual a-list bin table But that one will
be smaller memory wise and not in the hot path.

I am in the process of doing the implementation and will see if I can find
the optimal setting for all sizes which I can test. (basically to pin down
the strategy for each of the sizes 1,2,4,6,16,32,64,128,256, ... As the
size of the hash can only be in those sizes.

Oh also, for small hashes the hash is essentially a single association list
and superfast.

Maybe the dispatching overhead is too much, donough, perhaps trimming down
the features might be needed.

I will see if we can find some use of special assembler operations,
especially for small hashtables.

PRIMITIVES,
There are essentially three primitives
1. search        =  find a matching hash, return index or handle or #f
                           possible starting from a known position

2. add             =  add a new element that we now is not included
                           in the hashtable

3. search-list   = fast alist search in case of a small assoc list case
                          returns the key-val handle or #f possibly restarts
                          from a known index.

Possibly one may define a search-and-set-some primitive, e.g. one can
in hot cases not need to fhe the add afterwards and add is only used in the
slow path in a set operation. (For other operations it is in the fast path
though)

Happy Hacking!

Regards
Stefan

[-- Attachment #2: Type: text/html, Size: 7298 bytes --]

Re: Proposal for a new hash interface

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 6292 bytes --]

This is autogenerated code,

https://gitlab.com/tampe/guile-persist/-/blob/master/src/hash/macro.c

Not sure how well uint128_t works on my system, but the compiler should be
able to make this code run really fast. Anyhow it is quick matters to
change to uint64_t due to things not being hand coded. Can you see what I
am doing?

On Thu, Feb 24, 2022 at 1:07 AM Stefan Israelsson Tampe <
stefan.itampe@gmail.com> wrote:

> High all,
>
> I have taken the task to study a possible hash table implementation mostly
> in scheme but still speedy. I am still experimenting with different
> approaches. With managing code and iteration higher order functions in
> scheme and lower order implemented in C. I can match current hash
> implementations but with hash-fold and hash-for-each 10-20X faster and
> better semantics as it is not going via C.
>
> I suppose the implementation is more memory intensive than the current
> implementation. But much much safer and featurefull.
>
> So what are the features:
> * goops based organisation
>
> * allows one to type a hash table, e.g. disallow the use of
> different versions
>   of the assessors for the same hash.
>
> * surprisingly fast although we define goops methods for the accessors
>
> * A flag that indicates that (hash i) = i, for integers, which is used in
> python
>
> * Possible to freeze has hash e.g. it will not grow or shrink, when
> cleared only
>   all the values will be cleared.
>
> * A possibility to use (hash x (ash 1 60)) as a key, e.g. when checking if
> a slot
>   is equal, we compare only the long hash.
>
> * A proper separation between general code that can be pushed to C for
> speed    and scheme for nice integration and power
>
> Code:
>
> scheme:
> https://gitlab.com/tampe/guile-persist/-/blob/master/ice-9/hashish.scm
>
> C:
> https://gitlab.com/tampe/guile-persist/-/blob/master/src/hash/resize.c
>
> C/Scheme integration
> Each handle is of the form
> (hash key val)
>
> So when we store the key value pair we also store the hash values which are
> 60bit wide. This means that we can dispatch the search for an item using
> only the hash value and many operations can be done in a general way that
> can be pushed to C (if we want). So typically you first try to use C and
> when it finds a match you need to do the final check in scheme using the
> correct equal predicate. This means that we can achieve a very extensible
> system that you can extend without losing much performance. These
> primitives make the scheme code beautiful and well organized so we should
> probably keep this semantic even if we decide to do everything in guile
> scheme.
>
> Example, consider that we have designed a new hash table semantics. The
> easiest is to supply a hash function and a equal predicate like so
>
> (use-modules (ice-9 hashish))
> (use-modules (oop goops))
>
> (define (myhash    k s) ...)
> (define (myequal? x y) ...)
>
> (define-class <my-hash-map> (<stis-hash-map>))
> (stis-new-hash-type <my-hash-map> make-my-hash-table myhash myequal?
>      my-hash-ref  my-hash-set!  my-hash-remove!)
>
> Preferably when we do not need to know the type of the hashtable we can
> either use the methods (slow) stis-hash-ref stis-hash-set!
> stis-hash-remove!
>
> The fast way is to take advantage of the following construct,
> (define H (make-my-hash-table))
> (stis-with-hash-accessors (H : ref set remove)
>     ...
>     (set k1 (ref k2 #f))
>     ...
>     (remove k3)
>     ...)
>
> Both these methods are safe.
>
> There are some extra tools available.
>
> > stis-hash-resize!
> One can resize a hashtable as one likes
>
> > stis-hash-define-world!
> One can fill the hash table and then specify that this is the world. Then
> If all long hashes that are stored are unique, no equal method will be used
> for identity and the hashmap will be freezed
>
> > stis-hash-unworld-it
> Unset the world property (not yet coded)
>
> > stis-hash-copy
> Create a new hashtable (this is not yet coded)
>
> IMPLEMENTATION
> The implementation is not yet defined, we need to test it and try
> different versions. But One thing that one can notice are that by reducing
> the
> size if the hashtable one can speed up all operations. So the idea is to
> store
> a list of hash/index pairs in the hash and use varying sized cells for
> this. The
> smallest cell is 2 bytes and we can use more bytes for the index (size of
> hash table) and fewer for the hash itself) this means that we could use a
> size of 64 for the hash value and allow 1024 items in the hash table.
> Similarly as the hash  grows we will use 32bit cells and split the maximal
> size of the hashtable between the hash value and the hash table size. The
> next size is 64bit cells and the last one are 128 bit cells. There will be
> a fallback hash table which is the usual a-list bin table But that one will
> be smaller memory wise and not in the hot path.
>
> I am in the process of doing the implementation and will see if I can find
> the optimal setting for all sizes which I can test. (basically to pin down
> the strategy for each of the sizes 1,2,4,6,16,32,64,128,256, ... As the
> size of the hash can only be in those sizes.
>
> Oh also, for small hashes the hash is essentially a single association
> list and superfast.
>
> Maybe the dispatching overhead is too much, donough, perhaps trimming down
> the features might be needed.
>
> I will see if we can find some use of special assembler operations,
> especially for small hashtables.
>
> PRIMITIVES,
> There are essentially three primitives
> 1. search        =  find a matching hash, return index or handle or #f
>                            possible starting from a known position
>
> 2. add             =  add a new element that we now is not included
>                            in the hashtable
>
> 3. search-list   = fast alist search in case of a small assoc list case
>                           returns the key-val handle or #f possibly
> restarts
>                           from a known index.
>
> Possibly one may define a search-and-set-some primitive, e.g. one can
> in hot cases not need to fhe the add afterwards and add is only used in the
> slow path in a set operation. (For other operations it is in the fast path
> though)
>
> Happy Hacking!
>
> Regards
> Stefan
>
>
>
>
>

[-- Attachment #2: Type: text/html, Size: 8171 bytes --]