RFR: 8150676: Use BufferNode index

[Thomas Schatzl]

Hi,

On Tue, 2016-03-01 at 21:56 -0500, Kim Barrett wrote:
> Please review this change to PtrQueue and its derivatives to maintain
> the index in BufferNode where needed.  This allowed the removal of
> code to fill inactive leading portions of buffers with NULL and to
> remove code to skip over NULL entries.
> 
> Removed unused
> DirtyCardQueueSet::apply_closure_to_all_completed_buffers, 
> rather than fixing it's BufferNode manipulation.
> 
> Further changed SATBMarkQueue::filter to use two-fingered compaction,
> which may further reduce the number of writes to the buffer during
> filtering.  For example, using specjbb2015, with over 2.5M buffers
> processed, the number of writes using the new two-fingered compaction
> (12M) was a factor of 50 fewer than needed by the (non-NULLing)
> sliding algorithm (60M), and a factor of 250 fewer than the original
> sliding algorithm (330M).  On average, filtering a buffer removed
> about 75% of the entries in that test.
> 
> CR:
> https://bugs.openjdk.java.net/browse/JDK-8150676
> 
> Webrev:
> http://cr.openjdk.java.net/~kbarrett/8150676/webrev.00

These are general questions about the direction of your work in this
area. It's mostly about the pre-existing state, not about the changes
in particular:

  - do you intend to keep the use of void** and casting around in this
code? From what I understand, it would be much easier to read if the
PtrQueue were templatized on the element type. (Of course there are
probably many other options here to make this code nice like hiding a
generic void** QueueSet implementation as member of
dirtyCard/satbMarkQueue).

One could always, for the compiler, provide some void** getters. And
most likely the do not care what type of pointer the get anyway, as
long as it is pointer-sized.

  - the code does not fit the existing coding style guide. Like naming
(e.g. using "_sz" as member name), braces around single-line if
-statements and others.

Is there any intention of really cleaning up this code? And wouldn't it
be better to clean that up first instead of piecemeal changing stuff to
new style (with additional features) and old style in existing code?

That would simplify reviews a lot.

  - the conversion between BufferNode and PtrQueue elements using raw
void** and index parameters. Why not pass and return
PtrQueue/BufferNode? Also the use of the word "buffer" for basically a
generic buffer in comments and BufferNode seems to be a source of
constant confusion.
Also, "buffer" seems to sometimes also be interchangably used with
"Ptr/satbMarkQueue", which is pretty bad imo.
(I see that this change cleans that up quite a bit, so thanks for
that.)

I am asking myselves, wouldn't it be more useful to clean up that code
significantly once than trying to work around the existing
implementation while adding new features?

---- now for comments for the change:

  - I would really prefer that changes to the interface/cleanup would
be separate from the new feature (the two-finger compaction).
That would make reviewing much easier. :) See above.

This one, I think could be split into passing around BufferNode instead
of _buf and _index, and the two-finger-compaction. Maybe add some of
the other cleanup changes that do not change behavior to the second.

  - PtrQueue::flush_impl(), could you extract the condition _index ==
_sz into a method like is_empty()? I can't see anyone calling
is_empty() with a _buf that is NULL. Even then it should not matter.

  - all methods touched in a change should (if possible) adhere to
current coding standards. E.g. use of braces of one-line if-statement
bodies etc.

  - ptrQueue.hpp: deallocate_buffer, enqueue_complete_buffer:
description refers to non-existing arguments.

     process_or_enqueue_complete_buffer(): description is non
-descriptive.

  - PtrQueue::handle_zero_index(): the make_node_from_buffer() call can
be extracted out of the if-bodies.

pre-existing:
  - ptrQueue.cpp:214, typo in "enqueuing"; ptrQueue.cpp:220: missing
braces around if-body.

  - DirtyCardQueue::apply_closure() comment in the hpp file: I agree
that here, for clarity it would be better to refer to the member names
directly. At least indicate that the members of the buffers are meant
here.

Actually it seems to me that the "from index to size" is an
implementation detail of the queue, at least I would not understand
what "index" means for a typical queue.

I do not think there is something like a "false closure application".

  - DirtyCardQueue::apply_closure_to_buffer() interface: please put the
"size" parameter into a separate line (and name it "size").

What's an "active" element of BufferNode? BufferNode does not have any
notion of active elements. (Since BufferNodes is not documented at all,
it does not even have publicly accessible "elements").
Qualifying the entries from index to sz as "active" is not required
here imo. It's not referenced further anyway.

  - pre-existing: the "Override" comment over
DirtyCardQueueSet::mut_process_buffer does not have any meaning above
what the declaration already indicates.

  - dirtyCardQueue.hpp:138: "eleemnts" typo. I think it would be useful
to describe "completed" buffers and "active" elements somewhere. Like
in PtrQueue/BufferNode.

  - DirtyCardQueue.cpp:128: sz should be renamed to size and put into
an extra line.

  - DirtyCardQueue.cpp:131: braces around if-statement missing.

  - DirtyCardQueue.cpp:134: the code generally uses the postfix
increment in for-loops (yes, there are exceptions, but a grep for "i++"
gives 10 times more hits than "++i". (And fyi, "i += 1" is an ever
larger minority). Feel free to ignore though, not insisting on that.

  - in SATBMarkQueue::filter(): please extract the prefix decrement out
of the while loop.

  - as for the compaction algorithm, wouldn't the algorithm be easier
to read if the fingers went down from dst to src, moving either finger
depending on whether dst is reclaimable?

Something like (untested, may be complete garbage, may suffer from a
one-off problem):

dst--;
while (dst != src) {
  void* entry = *dst;
  if (retain_entry(entry, g1h)) {
    dst--;
  } else {
    *dst = *src; // one could be clever here and search up for a
retainable entry first - I do not think it matters much.
    src++;
  } 
}

The existing algorithm seems fine, but it contains a nested while, with
side-effects in the condition, and dependencies between the conditions.

Also, I would prefer if the closing brace of the while loop would be on
the next line.

  - it seems that *dst is never checked whether it should be retained.

  - satbMarkQueue.cpp:132, please add braces.

  - satbMarkQueue.cpp:132, I agree with Jon to use == in this case. The
">=" seems something you would always need to think about.

Thanks,
  Thomas