Re: [Sablevm-developer] Threading support in SableVM

[Etienne G. <gag...@uq...>]

Commenting on the summary.

Chris Pickett wrote:
> The problems seem to be in thread startup, and there might be something 
> wrong with splay_tree.c.  I put barriers in what I think are the right 
> places, so I don't think the problems are JMM-related.  I could be wrong 
> about this, especially if the splay_tree problem violates the JMM rules 
> about GC (see the "miscellany" at the end of the cookbook).

A splay tree is an unbalanced binary tree which has neat properties:
1- the cost of n operations (additions, searches, deletions) is
    O(n log n), or in other words, the *amortized* cost per operation
    is O(log n).
2- This tree has a "cache" property; every time a node is accessed, the
    tree is reorganized such that this node becomes root, this leads to
    a tree where frequently accessed nodes are near the root.  Empirical
    measurements show that this can result in much faster access than in
    traditional balanced binary trees (depends on the application, of
    course).

You probably noticed the important point above: the tree is modified on
all accesses.  This means that, in a concurrent setting, a "read lock" is
not sufficient to access the data structure.  Have you double checked that
your problem is not related to a concurrent or unsynchronized access to
a splay tree, somewhere in SableVM?  Maybe I forgot to acquire a lock
somewhere?

Etienne

-- 
Etienne M. Gagnon, Ph.D.             http://www.info.uqam.ca/~egagnon/
SableVM:                                       http://www.sablevm.org/
SableCC:                                       http://www.sablecc.org/