Status: New
Owner: ----
New issue 846 by bhackett1024: misnamed findGreatestLessThan in splay
benchmark
http://code.google.com/p/v8/issues/detail?id=846
I'm confused by the findGreatestLessThan function in the splay benchmark,
and am wondering if its behavior is intended. Contrary to its name, this
function returns the tree node with the greatest key less than or equal to
its parameter key. When used in the benchmark's kernel:
function SplayRun() {
// Replace a few nodes in the splay tree.
for (var i = 0; i < kSplayTreeModifications; i++) {
var key = InsertNewNode();
var greatest = splayTree.findGreatestLessThan(key);
if (greatest == null) splayTree.remove(key);
else splayTree.remove(greatest.key);
}
}
The behavior of findGreatestLessThan causes SplayRun to always remove the
node which was just inserted, so that the contents of the tree will be the
same after SplayRun as before (contrary to the comment). This seems a
pretty unrealistic way of testing insertion/removal performance. There's
also dead code --- the 'greatest == null' branch will never be taken, along
with all but the 'this.root_.key <= key' branch in findGreatestLessThan
itself (the findMax function referenced in findGreatestLessThan is never
defined).
This discrepancy is interesting mainly because whether the node removed is
the most recently added node or an arbitrary node has a big effect on the
performance of a generational GC (disclaimer: I've been doing some work on
Mozilla's mark/sweep GC).
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
