RFR: 8150676: Use BufferNode index

[Kim Barrett]

> On Mar 3, 2016, at 11:44 AM, Thomas Schatzl <thomas.schatzl at oracle.com> wrote:

Thanks for looking at this.  Comments inline.

I’m still testing updates, so a new webrev will come later.

> On Tue, 2016-03-01 at 21:56 -0500, Kim Barrett wrote:
>> 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).

There is only one cast left related to the element type:
DirtyCardQueue::apply_closure_to_buffer static_casts the current void*
element to jbyte*.  The element type for SATBBufferQueue *is* void*.
So I don't think there's a serious problem here.

> 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.

I dislike _sz and some similar naming choices too, and will probably
clean them up eventually.  I just hadn't intended to do that today.

> 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?

There's a lot of complexity in the code that I think isn't necessary,
but that makes some kinds of "simple cleanups" hard without first
refactoring various pieces.  For example, see the problems recently
encountered with changing some putative size and count values to use
unsigned types; it turns out that for some of them, a negative value
(always -1, I think) is effectively a flag requesting some different
behavior.

Some of the refactorings will likely make some cleanups of the current
code completely moot.  And there can also be ordering problems; for
example, some of my in-development changes in this area have gotten
deferred while waiting for that cleanup of some count and size values
to use unsigned types.

I've made several attempts at a thorough "cleanup" pass, but such
attempts keep getting out of hand and sending tendrils into all sorts
of unexpected places.  So for now I plan to continue making focused
incremental improvements.

> 
> 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?

Sorry, I'm not understanding what you are asking or suggesting here.

> Also the use of the word "buffer" for basically a
> generic buffer in comments and BufferNode seems to be a source of
> constant confusion.

I think this is mostly better now, with the more consistent use of BufferNode.
But let me know if you spot something still amiss.

> 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 see some places that use "the buffer" as a shorthand for "the buffer
currently associated with this queue".  I'm not bothered by that, if
it's clear from context.  Specific problematic uses?

> 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.

Whereas I see the two-finger compaction and similar changes to
eliminate unnecessary loads and stores as the point of this change,
with the consistent use of BufferNode and the associated index as part
of making that possible.

Because of that intent for this change, I've minimized extranious
unrelated changes / cleanups, and I may treat some of your suggestions
as such, though will note them for later.

> 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.

OK.

>  - 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.

We've discussed this before; the Hotspot coding style guide explicitly
permits brace-less one-line if-statements.  I know you dislike them.
You know I prefer them in some circumstances.  Let's move on.

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

I think you mean the references to "_sz" in the descriptions?  Those
aren't arguments, they are the _sz member.

>     process_or_enqueue_complete_buffer(): description is non
> -descriptive.

Indeed it is.  This function is on my refactoring hit list.  Out of
scope for this change.

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

Jon also mentioned this.  Another in-development refactoring will
probably undo that.

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

"enqueueing" and "enqueuing" are both valid spellings.  In hotspot
sources the former is more common than the latter, but both are in
use.  The PtrQueue code region consistently uses the former.

>  - 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.

Updated.  But it's not the members of the referenced buffer, but
rather the members of the queue object that are being referred to
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 did some rewriting here.

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

I think it's obvious from context, but ok. Revised.

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

Renamed to "buffer_size" rather than "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.

Revised for both apply_closure and apply_closure_to_buffer.  No longer
using that terminology.

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

That's pretty egregiously useless, and now gone.  I didn't replace it
with better text because I think this function will be going away.

>  - dirtyCardQueue.hpp:138: "eleemnts" typo.

Fixed.

> I think it would be useful
> to describe "completed" buffers and "active" elements somewhere. Like
> in PtrQueue/BufferNode.

Yes, it would.  Already on my todo list.  Out of scope for this change.

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

As earlier, renamed to buffer_size.

>  - 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.

C programmers are random about this, because in the default situation
it doesn't matter.  But because of operator overloading, it can make a
big difference for C++, where the recommended default usage is
pre-increment and pre-decrement.  I got into that habit a long time
ago, and have no interest in changing; although Hotspot mostly eschews
operator overloading, I might write non-Hotspot C++ code.

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

As noted in reply to Jon, I'm planning to use a slightly different
formulation.

>  - 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++;
>  } 
> }

Several problems:

- Doesn't appear to handle initial empty state.

- Doesn’t appear to test the final *dst.

- I disagree about "could be clever ... I do not think it matters
much"; I think it matters a lot.  Consider the case of a full buffer
that will be completely emptied by filtering, where this will store
every element into the last, doing buffer_size_in_elements useless
stores, instead of zero stores.

> 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.

Did you miss the retain_entry call here?
 131       while ((src < --dst) && retain_entry(*dst, g1h)) { }
The lhs of the && is sequenced before the rhs.  But the new version
doesn't have this line.

>  - 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