One of our applications makes fairly heavy use of hash-tables, and
forms similar to the above appear often. We're not aware of
performance bottlenecks but the implied "double traversal" through the
table rankles a little. (Actually, the double traversal is actually
happening, as lispworks' combination of macroexpander and compiler
isn't smart enough to coalesce this into a single search.)
I don't think there's any way around this idiom in Common Lisp (please
someone correct me if I'm wrong). Do / did other lisp variants offer
anything more?
define-modify-macro isn't the quite right thing (irrespective of
whether the compiler can do anything useful with the results) because
it always sets a new value.
- nick
From: Paul F. Dietz
Subject: Re: (or (gethash key table) (setf (gethash key table) new-value))
Date:
Message-ID: <uLqdnY-n1ZHV0d6iXTWJiw@dls.net>
Nick Levine wrote:
> I don't think there's any way around this idiom in Common Lisp (please
> someone correct me if I'm wrong). Do / did other lisp variants offer
> anything more?
Do the hash routines cache the search associated with the last key? If so,
the overhead is small. If it's an EQ or EQL hash table the caching is
straightforward; if it's an EQUAL or EQUALP hash table you can exploit
the fact that the key cannot be 'visibly modified', so you can cache
it using EQL.
Paul
"Paul F. Dietz" <·····@dls.net> writes:
> Nick Levine wrote:
>
> > I don't think there's any way around this idiom in Common Lisp (please
> > someone correct me if I'm wrong). Do / did other lisp variants offer
> > anything more?
>
> Do the hash routines cache the search associated with the last key? If so,
> the overhead is small. If it's an EQ or EQL hash table the caching is
> straightforward; if it's an EQUAL or EQUALP hash table you can exploit
> the fact that the key cannot be 'visibly modified', so you can cache
> it using EQL.
Actually, in the case of EQUAL or EQUALP, this belongs in a critical
section because the hash table could be filled by another task in a
multitasking situation. For the compiler to collapse this to a single
call would probably both be more efficient AND reduce the risk of
unwanted errors. It's theoretically possible but remarkably unlikely
that the programmer _intended_ to allow time for a race condition
between these two operations...
[Also, as to a cache, there are some issues of keeping it safe from
multitasking, not to mention the possibility of the key being
side-effected between the two calls (which is, by the way, legal,
though not recommended, if the key has not been previously stored...),
which would mean the cache value would be wrong unless the cache were
not EQ-based, in which case the cache test would slow down...]
Kent M Pitman wrote:
> the possibility of the key being
> side-effected between the two calls (which is, by the way, legal,
> though not recommended, if the key has not been previously stored...),
Are you sure this is the case? Section 18.1.2 says:
If an object O1 is used as a key in a hash table H and
is then visibly modified with regard to the equivalence
test of H, then the consequences are unspecified if O1,
or any object O2 equivalent to O1 under the equivalence
test (either before or after the modification), is used
as a key in further operations on H.
Note that it says used as a key, not used as a key for
a store operation. There is no requirement that the
key be present in the table.
Paul
Paul Dietz <············@motorola.com> writes:
> Kent M Pitman wrote:
>
> > the possibility of the key being
> > side-effected between the two calls (which is, by the way, legal,
> > though not recommended, if the key has not been previously stored...),
>
> Are you sure this is the case? Section 18.1.2 says:
>
> If an object O1 is used as a key in a hash table H and
> is then visibly modified with regard to the equivalence
> test of H, then the consequences are unspecified if O1,
> or any object O2 equivalent to O1 under the equivalence
> test (either before or after the modification), is used
> as a key in further operations on H.
>
> Note that it says used as a key, not used as a key for
> a store operation. There is no requirement that the
> key be present in the table.
Why would you arrive at such an interpretation? The requirement is
plainly so that if something is hashed into a certain bucket and a
side-effect would alter the bucket it belonged to, then you won't end
up having the thing live in a bucket that lookup will not seek. You
plainly can't mean that if I've ever done (gethash x y), I'm forbidden
from side-effecting x. I _routinely_ do things like
(let ((string-buffer (allocate-buffer-from-resource *string-buffer-pool*)))
(parse-token-into string-buffer stream)
(or (gethash string-buffer *known-tokens*)
(let ((permanent-string (copy-seq string-buffer)))
(setf (gethash permament-string *known-tokens*)
(make-token-named permanent-string)))))
in order to get a parser that conses only upon seeing genuinely
new tokens (as, I assume, READ does in many implementations).
I don't see any reason to suppose that my pre-check of GETHASH with
string-buffer should mean that the string-buffer is forbidden to be
used ever again as a string buffer (which I'm constantly refilling
with new program data and adjusting the string buffer on).
I assume "used as a key in a hash table H means "stored into", not
just "checked to see if it's stored into". The use of GETHASH does
not use it in a hash table, it verifies its non-use in a hash table.
···@ravenbrook.com (Nick Levine) writes:
> I don't think there's any way around this idiom in Common Lisp (please
> someone correct me if I'm wrong). Do / did other lisp variants offer
> anything more?
Although I doubt many (if any at all) do it, nothing keeps an
implementation from specially optimizing this idiom...
Put another way, the fact that it has to be spelled out long hand
does not imply that it must be a performance bottleneck. There may
be no way to make the 'spelling' any shorter, but the rest of your
message seems to provide a 'performance bottleneck' in the language
in general, which I don't think there is.