From: Nicolas Neuss
Subject: Ordering within maphash
Date: 
Message-ID: <877jnzy1tx.fsf@ortler.iwr.uni-heidelberg.de>
Hello,

when using maphash several times on an hash-table (without modifying it),
is it guaranteed that I obtain the key-value pairs always in the same
order?

This is probably non-standard and I should use another data-structure when
depending on ordering.  Nevertheless, I would be interested if there are CL
implementations out there which do not satisfy this condition.

Thanks, Nicolas.

From: Thomas A. Russ
Subject: Re: Ordering within maphash
Date: 
Message-ID: <ymiwtvz5dlc.fsf@sevak.isi.edu>
Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:

> 
> Hello,
> 
> when using maphash several times on an hash-table (without modifying it),
> is it guaranteed that I obtain the key-value pairs always in the same
> order?

No, it is not guaranteed.
It is highly likely that it would work in practice, but the standard
does not guarantee it and there are reasons why it may fail. (see Frode
Vatvedt Fjeld's answer)

-- 
Thomas A. Russ,  USC/Information Sciences Institute
From: Frode Vatvedt Fjeld
Subject: Re: Ordering within maphash
Date: 
Message-ID: <2hbrdbz884.fsf@vserver.cs.uit.no>
Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:

> when using maphash several times on an hash-table (without modifying
> it), is it guaranteed that I obtain the key-value pairs always in
> the same order?

At least not if you consider EQ or EQL hash-tables and their (quite
likely) having to be re-hashed in case of a GC cycle.

-- 
Frode Vatvedt Fjeld
From: Thomas A. Russ
Subject: Re: Ordering within maphash
Date: 
Message-ID: <ymizn0v5kht.fsf@sevak.isi.edu>
Frode Vatvedt Fjeld <······@cs.uit.no> writes:

> 
> Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:
> 
> > when using maphash several times on an hash-table (without modifying
> > it), is it guaranteed that I obtain the key-value pairs always in
> > the same order?
> 
> At least not if you consider EQ or EQL hash-tables and their (quite
> likely) having to be re-hashed in case of a GC cycle.

How likely is that?

I think that some (most?) implementations that use copying garbage
collectors are quite careful not to use the memory address of objects as
hash keys precisely to avoid the need to rehash on GC cycles.

-- 
Thomas A. Russ,  USC/Information Sciences Institute
From: Svein Ove Aas
Subject: Re: Ordering within maphash
Date: 
Message-ID: <coqc5p$lti$1@services.kq.no>
Thomas A. Russ wrote:

> Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> 
>> 
>> Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:
>> 
>> > when using maphash several times on an hash-table (without modifying
>> > it), is it guaranteed that I obtain the key-value pairs always in
>> > the same order?
>> 
>> At least not if you consider EQ or EQL hash-tables and their (quite
>> likely) having to be re-hashed in case of a GC cycle.
> 
> How likely is that?
> 
> I think that some (most?) implementations that use copying garbage
> collectors are quite careful not to use the memory address of objects as
> hash keys precisely to avoid the need to rehash on GC cycles.
>
How do you implement an EQ hash map without using memory addresses?
From: Frode Vatvedt Fjeld
Subject: Re: Ordering within maphash
Date: 
Message-ID: <2h3bynyvsf.fsf@vserver.cs.uit.no>
Svein Ove Aas <·········@aas.no> writes:

> How do you implement an EQ hash map without using memory addresses?

By storing a hash-key explicitly in each object.

-- 
Frode Vatvedt Fjeld
From: Frode Vatvedt Fjeld
Subject: Re: Ordering within maphash
Date: 
Message-ID: <2h7jnzyvts.fsf@vserver.cs.uit.no>
···@sevak.isi.edu (Thomas A. Russ) writes:

> How likely is that?

Fairly likely, I believe. I would certainly recommend against
depending on EQ hash-table ordering being preserved across GC for code
that's intended to be portable.

> I think that some (most?) implementations that use copying garbage
> collectors are quite careful not to use the memory address of
> objects as hash keys precisely to avoid the need to rehash on GC
> cycles.

They would be, but there are other concerns coming into play here. I'd
be very surprised to see an implementation that stores hash-key with
cons-cells, for instance. Of course, you'd want to mark the hash-table
"dirty" during GC, and only re-hash them lazily (as I think Duane
Rettig mentioned).

-- 
Frode Vatvedt Fjeld
From: Nikodemus Siivola
Subject: Re: Ordering within maphash
Date: 
Message-ID: <covf39$in6jf$2@midnight.cs.hut.fi>
Thomas A. Russ <···@sevak.isi.edu> wrote:

> I think that some (most?) implementations that use copying garbage
> collectors are quite careful not to use the memory address of objects as
> hash keys precisely to avoid the need to rehash on GC cycles.

Rehashing on table access is sufficient. This is what at least SBCL and
CMUCL do.

Cheers,

 -- Nikodemus
From: Nicolas Neuss
Subject: Re: Ordering within maphash
Date: 
Message-ID: <87zn0vwda8.fsf@ortler.iwr.uni-heidelberg.de>
Frode Vatvedt Fjeld <······@cs.uit.no> writes:

> Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:
>
>> when using maphash several times on an hash-table (without modifying
>> it), is it guaranteed that I obtain the key-value pairs always in
>> the same order?
>
> At least not if you consider EQ or EQL hash-tables and their (quite
> likely) having to be re-hashed in case of a GC cycle.

OK, implementations could cope with this by storing hash-keys with
instances or shifting objects only in such a way that the hash-key for the
address is not changed.  But probably this would be too much overhead or
too restrictive in general.  Maybe I should formulate my question in this
way: is there an implementation out there where the MAPHASH-order is kept
for EQ/EQL hash-tables in spite of GC?

Thanks, Nicolas.
From: Duane Rettig
Subject: Re: Ordering within maphash
Date: 
Message-ID: <4653jgtwe.fsf@franz.com>
Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:

> Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> 
> > Nicolas Neuss <·······@iwr.uni-heidelberg.de> writes:
> >
> >> when using maphash several times on an hash-table (without modifying
> >> it), is it guaranteed that I obtain the key-value pairs always in
> >> the same order?
> >
> > At least not if you consider EQ or EQL hash-tables and their (quite
> > likely) having to be re-hashed in case of a GC cycle.
> 
> OK, implementations could cope with this by storing hash-keys with
> instances or shifting objects only in such a way that the hash-key for the
> address is not changed.  But probably this would be too much overhead or
> too restrictive in general.  Maybe I should formulate my question in this
> way: is there an implementation out there where the MAPHASH-order is kept
> for EQ/EQL hash-tables in spite of GC?

Since you've now put the question into a positive light :-),
I can say that under certain circumstances, Allegro CL does this.

It all depends on the objects that are being used as keys.  Allegro CL
stores hash codes for some kinds of objects, such as symbols, function
objects, standard CLOS instances, and array headers, and in most cases
these hash values are used even by eq/eql hash-tables.  Also, hash codes
are generated for numbers per their value, not their address.  So when
any of these objects are used as keys in an eq/eql hash-table, they do
not "dirty" the hash-table for a gc.  [there are further measures we
take to avoid dirtying these hash-tables, but they are not relevant to
your question].

There is an internal function called excl::sxhash-if-fast, which is
the definitive determination of whether a hash-code will be
used/generated for a particular object [standard disclaimer: this
function is internal and thus not documented or supported; don't be
surprised if the name or interface changes in the future].  If this
function returns a value, then that value is the has value which will
be used in the eq/eql hash-table access, and it will not change.
Otherwise, the functon will return nil, and the address of the object
will be used (thus necessitating a rehash after some gcs).

CL-USER(1): (excl::sxhash-if-fast 'a)
7296848
CL-USER(2): (excl::sxhash-if-fast (cons 'a 'b))
NIL
CL-USER(3): (excl::sxhash-if-fast #'cons)
249
CL-USER(4): 

So to take advantage of this in the way you desire, simply be sure
all keys you have placed into your hash-table are only ones which
return a value from excl::sxhash-if-fast.  Note that the assumption
here is based on your original assertion that the hash-table is not
changed in other ways; if you add new key/value pairs to the hash-table,
then of course the order of access will change...

-- 
Duane Rettig    ·····@franz.com    Franz Inc.  http://www.franz.com/
555 12th St., Suite 1450               http://www.555citycenter.com/
Oakland, Ca. 94607        Phone: (510) 452-2000; Fax: (510) 452-0182   
From: Steven E. Harris
Subject: Re: Ordering within maphash
Date: 
Message-ID: <jk4d5xrs1mr.fsf@W003275.na.alarismed.com>
Ingvar <······@hexapodia.net> writes:

>         (setf ,keylist (sort ,keylist ,sort-fn &key ,key))
                                                 ^
                                                 |
 +-----------------------------------------------+
 |

That should be ":key", right? 

-- 
Steven E. Harris
From: Nicolas Neuss
Subject: Re: Ordering within maphash
Date: 
Message-ID: <87brdamdgy.fsf@ortler.iwr.uni-heidelberg.de>
Thank you for all the answers.

Nicolas.