|
From: Christoph B. <bar...@or...> - 2007-12-08 11:10:32
|
Am Samstag, 8. Dezember 2007 schrieb Julian Seward:
> > I don't get the assertion until some more stuff has been added to
> > the tree - the reason is that although the tree is out of order that
> > node is at the root and is therefore found without having to decide
> > which way to go.
>
> But the tree isn't out of order, is it? I thought what you established
> on the way to the station is that the ordering is signed word ordering,
> not unsigned, yes?
In my opinion the problem is, that you have lost transitivity. Assume Word is
only 8 bits wide.
The range is -128 ... 127
Now there are three numbers:
a = -100
b = 0
c = 100
a - b = -100 < 0 ==> b > a
b - c = -100 < 0 ==> c > b
c - a = 200 == -56 < 0 ==> a > c
If you put a, b, c in this order in an AVL-Tree you get:
a
/ \
c b
Because b > a and c < a. Now we add e = -1 and f = 1 into the tree and
get:
a
/ \
c b
/ \
e f
One additional node: g = -2 results in this tree:
a
/ \
c b
/ \
e f
/
g
Now we violate the AVL conditions at node a and we have to rotate. The result
will be:
e
/ \
a b
/ \ \
c g f
Now searching for c will not succeed because c > e.
I have changed the createSecVBitTable function to show this error:
static OSet* createSecVBitTable(void)
{
SecVBitNode * n;
Addr aAligned;
OSet * set = VG_(OSetGen_Create)( offsetof(SecVBitNode, a),
NULL, // use fast comparisons
VG_(malloc), VG_(free) );
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = 0x81000000;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = 0x0;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = 0x7F000000;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = 1;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = -1;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = -2;
VG_(OSetGen_Insert)(set, n);
aAligned = 0x0;
tl_assert2(VG_(OSetGen_Lookup)(set, &aAligned),
"Not found: %lu\n", aAligned);
aAligned = 0x7F000000;
tl_assert2(VG_(OSetGen_Lookup)(set, &aAligned),
"Not found: %lu\n", aAligned);
aAligned = 0x81000000;
tl_assert2(VG_(OSetGen_Lookup)(set, &aAligned),
"Not found: %lu\n", aAligned);
return set;
}
Greetings
Christoph
|
|
From: Christoph B. <bar...@or...> - 2007-12-08 19:29:11
|
Am Samstag, 8. Dezember 2007 schrieb Julian Seward: > > Yes. The relation established by the comparison function has to be > > transitive. This is not the case here. Therefore the function should not > > be used. > > > > I've shown how this affects the AVL tree in theory and implementation. > > This also fits one fact that Tom gives: There have to be additional > > additions and deletions to the tree till the values are not found. > > Below is a test program which compares comparison functions through > exhaustive testing. It shows immediately that the slow (reference) > and fast versions produce different results. > > We can fix Memcheck by falling back to the reference version, but I'd > like to see if there is a way to get the correct behaviour without > the extra conditionals. I would propose that you use a hashtable for the entries with one of the already used hashfunctions. You would get the following two benefits: - An amortized O(1) access time instead of O(log(n)) for all operations. - For some big programs (the ones I run) more than 70% of the memory consumption of memcheck is for the entries of secVBitTable2. Using a hashtable (preferably with a memory pool for the entries or a space efficient memory manager) would save about 16-24 bytes per entry. Christoph |
|
From: Nicholas N. <nj...@cs...> - 2007-12-08 23:12:13
|
On Sat, 8 Dec 2007, Christoph Bartoschek wrote: >> We can fix Memcheck by falling back to the reference version, but I'd >> like to see if there is a way to get the correct behaviour without >> the extra conditionals. > > I would propose that you use a hashtable for the entries with one of the > already used hashfunctions. You would get the following two benefits: > > - An amortized O(1) access time instead of O(log(n)) for all operations. > > - For some big programs (the ones I run) more than 70% of the memory > consumption of memcheck is for the entries of secVBitTable2. Using a > hashtable (preferably with a memory pool for the entries or a space efficient > memory manager) would save about 16-24 bytes per entry. I just spoke with Julian. For this release, we're just going to use the slower version that is correct. Any other change is too big at this late stage. After the release, we can look at using a hashtable instead. Christoph, if you are able to try using the hashtable instead and give us some performance numbers and a patch, that would be very helpful. Nick |