回复: [EXT] Re: Follow-up results for SwissTable with Vector API

[Zhu, Yifan]

I am confused. It seems that my replies are detached from the mailling list. It that expected?


[cid:c701634b-974a-4880-b982-6536b5c875d0]
Schrodinger ZHU Yifan, Ph.D. Student
Computer Science Department, University of Rochester

Personal Email: i at zhuyi.fan
Work Email: yifanzhu at rochester.edu
Website: https://www.cs.rochester.edu/~yzhu104/Main.html
Github: SchrodingerZhu
GPG Fingerprint: BA02CBEB8CB5D8181E9368304D2CC545A78DBCC3

[cid:d126ffb1-dd3b-4bf6-955f-f3cbfc8c2035]
________________________________
发件人: panama-dev <panama-dev-retn at openjdk.org> 代表 Paul Sandoz <paul.sandoz at oracle.com>
发送时间: 2023年1月6日 0:29
收件人: Zhu, Yifan <yzhu104 at UR.Rochester.edu>
抄送: panama-dev at openjdk.org <panama-dev at openjdk.org>
主题: [EXT] Re: Follow-up results for SwissTable with Vector API

Hi,

I saw you sent another email prior to this, but for some reason it got lost by the moderation system. (Since you are not a member of the list the emails need to be moderated and approved.)


> On Jan 5, 2023, at 8:09 AM, Zhu, Yifan <yzhu104 at UR.Rochester.edu> wrote:
>
> This is the following up message for https://urldefense.com/v3/__https://mail.openjdk.org/pipermail/jdk-dev/2023-January/007288.html__;!!CGUSO5OYRnA7CQ!c6-WVSHfkvXgbKEtNWhxgdZ9EHDDMbmUz9AbxpvbYN54xt_4LzTwYJd4PdHmueDBCmryWsWBXfjE-Jpw_Cfrf6WyAw$ .
>
> > You do:
> >  converted.intoMemorySegment(MemorySegment.ofArray(control), offset, ByteOrder.nativeOrder());
> >
> > Can you just do:
> >
> >  converted.intoArray(control, offset);
>
>
> I did so because I found that Vector<Byte> actually does not have that method.

Ah, yes. There could be an perf issue with memory segment access, although since you had to wrap the array in a segment there will be some cost to that. It’s like if you wrapped the control array in a segment and stored in a field it would work better.


> After your suggestion, I switched to use ByteVector instead by Vector<Byte>. Surprisingly, this time the hashmap delivers a better performance. It 2~3 times faster during the insertion procedure.

Good!


> However, there was still a performance gap behind the standard hashmap during finding precedure.
>
> For the ease of discussion, I attach the relevant code here:
>
> private int findWithHash(long hash, K key) {
>     byte h2 = Util.h2(hash); //highest 7 bits
>     int position = Util.h1(hash) & bucketMask; // h1 is just long to int
>     int stride = 0;
>     while (true) {
>         var mask = matchByte(position, h2).toLong(); // match byte is to load a vector of byte and do equality comparison
>         while (MaskIterator.hasNext(mask)) {
>             var bit = MaskIterator.getNext(mask);
>             mask = MaskIterator.moveNext(mask);
>             var index = (position + bit) & bucketMask;
>             if (key.equals(keys[index])) return index;
>         }
>
>         if (matchEmpty(position).anyTrue()) {
>             return -1;
>         }
>
>         stride += VECTOR_LENGTH;
>         position = (position + stride) & bucketMask;
>     }
> }
> From Intellij IDEA's profiler, it seems that a large portion of time is spent on building the vectormask. I see there is an underlying bTest operation converting the results to boolean array and then give the mask. Will this be internally optimized to a single movemask operation by JVM?
>

Can you get an inline/compilation trace like you did for insert?

The VectorMask.toLong method is an intrinsic method.

Try:

  var vmask = matchByte(position, h2);
  var mask = mask.toLong();

Probably will not make any difference, but if the findIInsertSlot performed ok operating on the mask returned from matchEmptyOrDelete it points to an issue with VectorMask.toLong.

Paul.

>
> <Outlook-ejiaczyb.png>
> Schrodinger ZHU Yifan, Ph.D. Student
> Computer Science Department, University of Rochester
>
> Personal Email: i at zhuyi.fan
> Work Email: yifanzhu at rochester.edu
> Website: https://www.cs.rochester.edu/~yzhu104/Main.html
> Github: SchrodingerZhu
> GPG Fingerprint: BA02CBEB8CB5D8181E9368304D2CC545A78DBCC3
>
> <Outlook-3nrq0klq.svg>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/panama-dev/attachments/20230105/5b40d3da/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Outlook-3cjuahvq.png
Type: image/png
Size: 19680 bytes
Desc: Outlook-3cjuahvq.png
URL: <https://mail.openjdk.org/pipermail/panama-dev/attachments/20230105/5b40d3da/Outlook-3cjuahvq-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Outlook-fjqcbbcv
Type: image/svg+xml
Size: 41432 bytes
Desc: Outlook-fjqcbbcv
URL: <https://mail.openjdk.org/pipermail/panama-dev/attachments/20230105/5b40d3da/Outlook-fjqcbbcv-0001.svg>