Follow-up results for SwissTable with Vector API

[Zhu, Yifan]

This is the following up message for https://mail.openjdk.org/pipermail/jdk-dev/2023-January/007288.html.


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


[cid:4401acf2-1a73-4907-9076-ac2a0432d6d7]
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:c985ec55-2a1a-4640-9eca-cd7741cf83f1]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/panama-dev/attachments/20230105/4687b940/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Outlook-ejiaczyb.png
Type: image/png
Size: 19680 bytes
Desc: Outlook-ejiaczyb.png
URL: <https://mail.openjdk.org/pipermail/panama-dev/attachments/20230105/4687b940/Outlook-ejiaczyb-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Outlook-3nrq0klq
Type: image/svg+xml
Size: 41432 bytes
Desc: Outlook-3nrq0klq
URL: <https://mail.openjdk.org/pipermail/panama-dev/attachments/20230105/4687b940/Outlook-3nrq0klq-0001.svg>