Steel Bank Common Lisp

Nikodemus Siivola wrote:
> I bet what is happening is this:
>
> 1. Thread 1 asserts that value is a number, and writes it to table
> under the key.
>
> 2. Thread 2 calls REMHASH with the same key and table (somewhere else
> in the code.)
>
> 3. Thread 1 tries to read the value back from the table, and discovers
> it gone. Ooops.
>
> Having the table synchronized doesn't magically guarantee that the
> (SETF GETHASH) and GETHASH calls in the above segment are executed
> without other threads operating on the table.
>
> Use WITH-LOCKED-HASH-TABLE to group multiple read/write operations on
> a single hash-table:
>
> (with-locked-hash-table (ht)
>   (assert (numberp value))
>   (setf (gethash key ht) value)
>   (assert (numberp (gethash key ht))))
>
> guarantees that the second ASSERT will not fail if the first on did
> not. Assuming the table is synchronized, this excludes not only other
> WITH-LOCKED-HASH-TABLE sections using the same table, but all of (SETF
> GETHASH), GETHASH, CLRHASH, and REMHASH for the duration.
>   

What I found surprising is that there is no REMHASH anywhere in my code; 
the threads just write to that hash table, and the values are always 
numbers, so once an entry contains a number, that number might change 
but never disappear. Or so I thought.
So, if I understand what you are saying:
1. thread 1 writes to the table
2. thread 2 wants to write to that same key, and this, it seems, implies 
first removing the former entry and then creating a new one; sometimes 
it happens that thread 1 reads from the table in between these two 
operations, and finds nothing.
Is that correct?

giovanni

On 21 April 2010 18:02, Giovanni Gigante <giov@...> wrote:

> But what happens is that, once in a while (say once in 2000 times or
> so), writing to the hash table seems to fail silently. That is, inside
> one thread:
>
> (let ((value (a-double-float-obtained-by-a-complicated-computation))
>      (key (a-nested-simple-vector-of-integers))) ; different threads
> may happen to use the same key.
>  (assert (numberp value)) ; this always passes, as expected
>  (setf (gethash key ht) value)
>  (assert (numberp (gethash key ht)))) ; once in a while this fails;
> gethash returns NIL NIL.
>
> Is it possible that this is a bug in synchronized hash tables?

Possibly, but unlikely.

I bet what is happening is this:

1. Thread 1 asserts that value is a number, and writes it to table
under the key.

2. Thread 2 calls REMHASH with the same key and table (somewhere else
in the code.)

3. Thread 1 tries to read the value back from the table, and discovers
it gone. Ooops.

Having the table synchronized doesn't magically guarantee that the
(SETF GETHASH) and GETHASH calls in the above segment are executed
without other threads operating on the table.

Use WITH-LOCKED-HASH-TABLE to group multiple read/write operations on
a single hash-table:

(with-locked-hash-table (ht)
  (assert (numberp value))
  (setf (gethash key ht) value)
  (assert (numberp (gethash key ht))))

guarantees that the second ASSERT will not fail if the first on did
not. Assuming the table is synchronized, this excludes not only other
WITH-LOCKED-HASH-TABLE sections using the same table, but all of (SETF
GETHASH), GETHASH, CLRHASH, and REMHASH for the duration.

Cheers,

 -- Nikodemus

On 30 April 2010 12:27, Giovanni Gigante <giov@...> wrote:

> What I found surprising is that there is no REMHASH anywhere in my code;

That is indeed surprising.

> the threads just write to that hash table, and the values are always
> numbers, so once an entry contains a number, that number might change
> but never disappear. Or so I thought.

Yes, that should be the case. (SETF GETHASH) overwrites the last
entry, and :SYNCHRONIZED T should be enough to guarantee that other
readers don't see the table in an inconsistent state.

About the only thing I can think of that could be causing trouble is
violating CLHS 3.6:

"Hash-table traversal

  For hash table traversal operations, new elements may not be added
or deleted except that the element corresponding to the current hash
key may be changed or removed."

The important thing is that this applies to all threads. See MAPHASH docstring:

"Consequences are undefined if HASH-TABLE is mutated during the call to
MAPHASH, except for changing or removing elements corresponding to the
current key. The applies to all threads, not just the current one --
even for synchronized hash-tables. If the table may be mutated by
another thread during iteration, use eg. SB-EXT:WITH-LOCKED-HASH-TABLE
to protect the MAPHASH call."

So if you have a thread using MAPHASH or WITH-HASH-TABLE-ITERATOR and
another thread writing to the same table in parallel, that could be
the source of your troubles. In that case, add WITH-LOCKED-HASH-TABLE
around the MAPHASH/W-H-T-I.

If hash table iteration is not involved, I'm stumped right now.

Cheers,

 -- Nikodemus

Nikodemus Siivola wrote:
> If hash table iteration is not involved, I'm stumped right now.

Unfortunately, no hash table iteration is in play either. I really can't 
understand what's going on, and any attempt at reproducing the issue in 
a less complicated context have not succeeded so far.
In practice I have eliminated the problem by protecting the hash table 
writes with a mutex, but the mistery remains.
I'll let you know if I manage to produce a succesfully unsuccessful test 
case.

Giovanni