opencog-dev team mailing list archive

["Linas Vepstas" <linasvepstas@xxxxxxxxx>]

2008/9/30 Borislav Iordanov <borislav.iordanov@xxxxxxxxx>:
>
>
> I'm not sure I understand. Atoms may well be immutable, but
> hypergraphs aren't. When a thread (a MindAgent) adds a bunch of atoms
> in a sequence, it's the same thing as a thread making several
> modifications and leaving the common data structure (the hypergraph)
> in an inconsistent state: another thread could do a lookup for an atom
> with certain criteria and make wrong assumptions because the first
> thread hasn't finished the hypergraph update.

What you describe would be a simple programming error
on the part of whoever wrote the such mind-agents. It would
be quite easy to fix.

The problem that I'm concerned about is at a different level.
Say that some process, after completing its work, is deleting
a bunch of stuff. For example, say the NLP subsystem is
done processing a bunch of sentences, and so these need
to be deleted. No other process will access these sentences,
so this should not be a problem.

However, there is another process that is working with
WordNodes (which exist independently of the sentences
they're in -- they're essentially "permanent" nodes).
Operations on word nodes typically require that the
incoming set  of the word node to be traversed, so
as to find some link, of some given type.  Traversal
of the incoming set is a walk over HandleEntries.
(which are linked lists)

Now, the sentences being deleted will show up in this
list of HandleEntries (if the word appeared in that
sentence). If its HandleEntry is deleted in one thread
while another thread is innocently dereferencing it ...
Ka Booom!

Thus, the locking problem in opencog would require
locks on HandleEntry lists (including those that were
dynamically generated, on the fly, by queries). Finding
all of these are non-trivial; the performance hit is
non-trivial.  There are other issues: you can't just lock
a list and leave it locked ... it may take seconds or
minutes to iterate over a list; so we'd really need to
lock and unlock in the iterator, per-each-HandleEntry.
That's a major performance hit.

> If you want to deal with multi-threading in general, and insulate the
> MindAgent programmer from having to worry about it, software
> transactional memory (STM) would be a better strategy, IMHO.

Hmmm. Maybe. But the onus is not on the MindAgent
programmer, and in the problem I describe, there's nothing
that the MindAgent programmer can do to solve it. Its occuring
at a deeper, more primitive level.

In fact, I am not sure how STM applies. Say, I'm traversing
a linked list. Before I get the "next pointer", I check the
transaction log to make sure its not deleted. Then I write
to the transaction log to say "I'm using this Handle entry
now so you can't delete it". Then, when I'm done using it,
I mark it unused. Meanwhile the thread that's trying to
delete it is spinning, waiting for it to become free?  This
seems to require all sorts of locking, and worse, spinning.
So naively, this doesn't seem to work, not in this way.

> But, you'd wipe out most of the performance benefits of C++ because
> that would mean that people can't control memory usage by themselves.

But that's not the problem! The locking problem is a *much*
worse performance hit than GC could ever be, or so it seems
to me -- the issue is not the performance of the GC, but
the performance of multi-threading.

In a certain sense, that's *the whole point* behind STM and
GC: GC can be regarded as a way of implementing STM:
it is "always" (cough cough) safe to dereference an object
in a garbage collected system, because it's guarenteed not
to disappear out from under you. Thus, you can perform
the kinds of "optimisitic" changes that STM is talking about
without fear of dereferencing a bad pointer; when you are
done manipulating your object, the "commit" phase is
nothing more than placing a pointer to the object back in
the database, which can be done lock-free.

--linas