[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openjdk-hotspot-runtime-dev
Subject:    Re: BitMap vs VectorSet?
From:       "Liu, Xin" <xxinliu () amazon ! com>
Date:       2022-10-31 16:56:54
Message-ID: 834b6a72-1459-a00e-3fc3-19f3432d4ea5 () amazon ! com
[Download RAW message or body]

[Attachment #2 (multipart/mixed)]

[Attachment #4 (multipart/mixed)]


hi, John,

Thank you for your pointer. It makes a lot of sense.  I also prefer
BitMap rather than VectorSet. I check who is including 'vectset.hpp'.
They are all from C2 compiler except 'share/ci/bcEscapeAnalyzer.hpp'.

I manage to change VectorSet to BitMap in Unique_Node_List. It's not
drop-in substitution. The interfaces are different. VectorSet is
elastic. eg. VectorSet::test returns false when index is out of range.
It can automatically grow to the specified index in VectorSet::test_set.
 Storage-wise, VectorSet supports both Resource and Arena but
ResourceBitMap and ArenaBitMap are two independent classes in bitMap.hpp.

I will file a JBS to fill the gap first.

Here is what I have done. It doesn't create any trouble after
substitution. of course, we are going to test it thoroughly.

https://github.com/openjdk/jdk/compare/master...navyxliu:jdk:refactor_bitmap

thanks,
--lx


On 10/27/22 11:07 AM, John Rose wrote:
> CAUTION: This email originated from outside of the organization. Do not click links \
> or open attachments unless you can confirm the sender and know the content is safe. \
>  
> 
> This is a good question, and a reasonable time to engage with it as well.
> 
> The code in src/hotspot/share/libadt is very old (~30 years) and has not been \
> vigorously maintained, relative to changes in C++ practice. 
> BitMap is newer and its code is more modern and actively maintained.  (Thanks Kim \
> B. et al.)  In my opinion, it deserves to be used instead of VectorSet.  Having two \
> classes for the same set of tasks is technical debt.  It is the sort of thing that \
> naturally happens on a large project when two groups settle on different solutions \
> for a common problem.  And the sort of thing a large project has to clean up over \
> time. 
> So, I support taking steps (reasonable, gradual, limited-impact steps) to retire \
> the classes in libadt, replacing them with more modern ones, in \
> src/hotspot/share/utilities. 
> As you note, Xin, this is somewhat more urgent as we increase our gtest coverage, \
> since we don't want to develop two sets of new tests for the same application area. \
>  It's also more urgent as hardware technology advances:  If we choose to work \
> harder to vectorize bitset operations, we don't want to do that work twice. 
> It's also more urgent as software technology advances.  I'm reminded that there are \
> many new algorithms for bit-twiddling (the name Daniel Lemire comes to mind, for \
> one) and (again: get the pattern?) we don't want to upgrade the algorithms twice. 
> People working on HotSpot routinely deal with extremely challenging software \
> problems, specific to optimization, garbage collection, concurrency, platform \
> support, performance, and more.  It's hard to always, also, select well-tested, \
> well-designed shared libraries to help with these problems; sometimes you just have \
> to roll your own.  But while understandable, that tends to create technical debt.  \
> That sometimes leads to failures (unscheduled payments on technical debt) due to \
> lack of test coverage, simply because some work somewhere didn't use common code \
> but "rolled their own" algorithms. 
> So, yes, let's double down on BitSet and retire VectorSet.
> 
> (And Dict, while we are at it: There are some really nice hash table classes \
> developed recently by the runtime group; surely we are not too far from merging the \
> job of Dict into that group of classes?) 
> — John
> 
> On 27 Oct 2022, at 0:07, Liu, Xin wrote:
> 
> > hi,
> > 
> > Recently, I extended VectorSet(libadt/vectset.hpp) to support
> > intersection. Then I found that there is yet another "vector set" called
> > 'BitMap'. From my reading, the data structure of BitMap is same as
> > VectorSet. BitMap has already supported intersection/union/difference
> > and it even owns corresponding gtests.
> > 
> > Given that, why does HotSpot still need to maintain both VectorSet and
> > BitMap? I grep VectorSet and there are still many references. Is that
> > too troublesome to replace VectorSet with BitMap or there are other
> > reasons?
> > 
> > I modified VectorSet because Unique_Node_List(node.hpp) uses it. I
> > hesitate now. Should I invest a new gtest for the new code or I just use
> > BitMap instead?
> > 
> > thanks,
> > --lx


["OpenPGP_0xB9D934C61E047B0D.asc" (application/pgp-keys)]
["OpenPGP_signature.asc" (application/pgp-signature)]

[prev in list] [next in list] [prev in thread] [next in thread]