<!DOCTYPE html><html><head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body><div style="font-family: sans-serif;"><div class="plaintext" style="white-space: normal;"><p dir="auto">In the C# code I see some familiar things in strange C# clothing.
<br>
There are a number of length-256 tables accessed by (unsigned?)
<br>
bytes or by chars that have been guarded to the range 0..255.
<br>
Access to them is not range-checked (pointer arithmetic + load).</p>
<p dir="auto">Here is what I think is a representative bit:</p>
<blockquote style="margin: 0 0 5px; padding-left: 5px; border-left: 2px solid #777777; color: #777777;"><p dir="auto">Vector128<byte> compactmask = Vector128.Load(tablePtr + pop1 * 8);
<br>
Vector128<byte> answer = AdvSimd.Arm64.VectorTableLookup(pruned.AsByte(), compactmask);</p>
</blockquote><p dir="auto">Using a scalar value “pop1” as index, you need to load a permutation
<br>
vector (or some such thing) from a static table. Then you apply that
<br>
vector to a data vector “pruned” to transform to the desired answer.</p>
<p dir="auto">I think what we are building now is a primitive VectorTableLookup
<br>
primitive in our Vector API. There is a question about how to
<br>
handle out-of-range indexes in the permutation (lookup/table)
<br>
vector; what is the policy for VectorTableLookup? Undefined
<br>
behavior? Masking to power of two?</p>
<p dir="auto">The compactmask thingy (it’s not a mask is it?) appears to be a
<br>
permutation vector, what we’d call a VectorShuffle, extracted
<br>
from a static table. We don’t have a fast way to do this yet,
<br>
because our memory access story is accompanied by low-level
<br>
safety checks almost everywhere.</p>
<p dir="auto">I think, as a general principle for APIs to be used for
<br>
these algorithms, we should be masking both permutation indexes,
<br>
and table indexes, to powers of two, as a way of avoiding more
<br>
complicated range checks.</p>
<p dir="auto">Thus, if we load an unconditioned vector from memory and use it
<br>
as a shuffle (LUT) then we may need to apply a VPAND to it to force
<br>
the indexes into the right place. And when we load such a thing,
<br>
either a shuffle or some other random datum, we should consider
<br>
reducing the index using a scalar AND operation, instead of doing
<br>
the usual Java thing of range-check-and-throw.</p>
<p dir="auto">A VectorShuffle object is preconditioned, range checked at construction.
<br>
But if you convert it from a vector, you have to do the range check
<br>
dynamically. I think maybe we need a conversion that boils down to
<br>
a VPAND, and sometimes (if the JIT sees a suitably conditioned input)
<br>
a NOP.</p>
<p dir="auto">When such things (vector or shuffle) are loaded from memory, either
<br>
they are pointer-indirected (so shuffles have their preconditioning),
<br>
or if they are flat, they are loaded from segments or arrays, and
<br>
there is no preconditioning.</p>
<p dir="auto">I think maybe we need a new kind of object which acts as a static
<br>
fixed-size (power of two size) table of VectorShuffle objects,
<br>
all of which are preconditioned for instant use with whatever VPERM
<br>
operation the hardware supplies. A value loaded from such a table
<br>
would not need a VPAND to ensure correct index format.</p>
<p dir="auto">Moreover I’m envisioning statically definable tables of BOTH vectors
<br>
per se and their shuffles (validated permutation/rearrange/lookup tables).
<br>
And implementations of them for each vector species of course.</p>
<p dir="auto">This is a fair amount of design work. As a shortcut, I think we should
<br>
support appropriate tools for third parties (like your team Daniel)
<br>
to build such things. I think an unchecked memory segment might be
<br>
a good place to store such tables, and for prototyping one might
<br>
consider digging into internal (post-guard) access subroutines
<br>
like fromMemorySegment0Template.</p>
<p dir="auto">I think we might also need an unsafe bridge between vectors and shuffles,
<br>
one which converts bitwise between them, and does not bother to re-impose
<br>
range checks on the shuffle lanes (permutation indexes). That way,
<br>
a fast, flat container for vectors could be wrapped as a fast, flat
<br>
container for shuffles.</p>
<p dir="auto">There are a number of bits here which are hard to access (buried
<br>
in the implementation) or even missing. Eventually I’d like to
<br>
build on top of them (perhaps adding missing bits) to expose
<br>
static lookup tables that can serve vectors and shuffles.</p>
<p dir="auto">And if that is useful, one might also consider a third kind of
<br>
table that is the target of a gathering store, where each table
<br>
entry is indexed by both lane position and lane contents.
<br>
Like the other two, it would internally use unsafe access
<br>
and guard against OOB errors by masking down the query index.
<br>
In this case, the masking would be applied across all the
<br>
lanes, since it is a multi-index operation.</p>
<p dir="auto">Finally, such static tables are a place where Java’s lambdas
<br>
could shine, as compact specifications of the table contents.
<br>
When reading the above C# code it is clear to me that the
<br>
tables were not manually written, but emitted by some ad
<br>
hoc program. A good Java way to build such tables is to
<br>
supply a constructor argument that is a lambda which is
<br>
iterated over the table’s index space to obtain each table
<br>
value.</p>
<p dir="auto">Let’s think some more about this stuff. I think static
<br>
tables are an under-appreciated tool for these kinds of
<br>
algorithms.</p>
<p dir="auto">— John</p>
<p dir="auto">On 16 Sep 2024, at 11:08, Daniel Lemire wrote:</p>
</div><blockquote class="embedded" style="margin: 0 0 5px; padding-left: 5px; border-left: 2px solid #777777; color: #777777;"><div id="C0FA6312-8035-4456-B636-026DB8FF68EE">
<div>For reference, we have published a C# library for Base64 decoding:<br></div>
<div><br></div>
<div><a href="https://github.com/simdutf/SimdBase64">https://github.com/simdutf/SimdBase64</a><br></div>
<div><br></div>
<div>This is another example of a library that cannot be written (with good performance) in Java right now.<br></div>
<div><br></div>
<div>I thought it might be useful to provide another example.<br></div>
<div><br></div>
<div>(Note that I am *not* biased in favour of C# nor am I promoting C#. I am only using C# as a reference due to the obvious similarity between C# and Java.)</div>
<div><br></div>
<div>- Daniel</div>
<div><br></div>
<div>On Fri, Jun 28, 2024, at 12:51, Paul Sandoz wrote:<br></div>
<blockquote type="cite" id="qt" style="">
<div><br></div>
<div><br></div>
<div>> On Jun 28, 2024, at 9:36 AM, Chris Hegarty <<a href="mailto:chegar999@gmail.com">chegar999@gmail.com</a>> wrote:<br></div>
<div>> <br></div>
<div>> Hi,<br></div>
<div>> <br></div>
<div>> <br></div>
<div>> On 21/06/2024 21:11, Paul Sandoz wrote:<br></div>
<div>>> Hi Daniel,<br></div>
<div>>> Thanks for the email discussion. I think we can do better and get to, or closer to, your expectation on the generation of a single instruction.<br></div>
<div>>> At the moment rearrange performs bounds checks on the shuffle argument (checking for exceptional indexes), and selectFrom converts a vector to a shuffle and calls rearrange. <br></div>
<div>> <br></div>
<div>> ...<br></div>
<div>> <br></div>
<div>> We've run into this separately too. If memory serves me correctly, it was slice(int) using rearrange internally to only then do expensive bounds checks on the implementation specific shuffle. ( I can try to dig out the details if I've mixed up something here. )<br></div>
<div>> <br></div>
<div><br></div>
<div>Please share if you can (I recall you may have mentioned this to me in the past, and I probably said “hmm…. this is tricky"). Benchmarks/code can really help focus our efforts.<br></div>
<div><br></div>
<div><br></div>
<div>> Bounds checks on input at the API level is expected, but not when the rearrange is an implementation detail.<br></div>
<div>> <br></div>
<div>> More generally, the system property has been around for a while now, and from my understanding it's a workaround to the compiler not yet being able to eliminate the checks. Firstly, is this understanding correct? And if so, is the intention to eventually remove it when it is no longer needed?<br></div>
<div>> <br></div>
<div><br></div>
<div>The system property is for debugging, it’s not intended for production use. Ideally it would go away, but it’s a useful "break glass in emergency". My usage was intended to show what might be possible if we can enhance the API and/or implementation appropriately.<br></div>
<div><br></div>
<div>Paul.<br></div>
<div><br></div>
<div>> ...<br></div>
<div>> <br></div>
<div>> > To be fair, it is fine if folks say "No, we don't want to do this with Java Vector, we don't want to optimize indexing in Lucene, we want to do X".<br></div>
<div>> <br></div>
<div>> Lucene is already using the Panama Vector API to improve the performance of vector similarity comparisons - for vector search. We would love to use it for more, but are largely hampered by the above issue. A less ideal situation is that in Elasticsearch [1] we're now using Panama FFI to workaround the limitations of the Vector API by linked to our own optimized implementations. This not ideal, and effectively robs Lucene of these potential performance benefits (since it's non-trivial to ship Lucene with a native lib)<br></div>
<div>> <br></div>
<div>> -Chris.<br></div>
<div>> <br></div>
<div>> [1] <a href="https://urldefense.com/v3/__https://github.com/elastic/elasticsearch/tree/main/libs/simdvec__;!!ACWV5N9M2RV99hQ!OZZEZlRHgbdC6YncLGIyD41hdpE2pHOo9-alCbMm7qzTPbmxPPLN1-IzNwnemXh3PnfOwsjdiwb5Qzrw4EM$">https://urldefense.com/v3/__https://github.com/elastic/elasticsearch/tree/main/libs/simdvec__;!!ACWV5N9M2RV99hQ!OZZEZlRHgbdC6YncLGIyD41hdpE2pHOo9-alCbMm7qzTPbmxPPLN1-IzNwnemXh3PnfOwsjdiwb5Qzrw4EM$</a> <br></div>
<div><br></div>
<div><br></div>
</blockquote>
<div><br></div></div></blockquote>
<div class="plaintext" style="white-space: normal;">
</div>
</div></body>
</html>