a value from one location to another (register or
>> memory). Tantivy uses this for skipping through postings, in a single
>> layer in-memory skip list structure (versus Lucene's on-disk
>> (memory-mapped, by default) multi-layer skip list) -- see the above blog
&g
>
> Wow, this looks very relevant to Lucene! Could this index be used for
> faster implementation of our skip lists? Even though they are static
> (computed once at segment-write time) vs dynamic/online that these learned
> indices are also able to handle, it looks like learned indices are still
On Sun, Jul 30, 2023 at 11:17 AM Bruno Roustant
wrote:
Interesting coincidence, I'm currently working on a learned index on sorted
> keys that can advantageously replace binary search.
> It is very compact (additional space of 2% of the sorted key array, e.g.
> 40KB for 200MB of keys), and it is
On Fri, Jul 28, 2023 at 7:04 AM Dawid Weiss wrote:
> Actually this is exactly the same for Java:
>>
> Yup, I know (we all know by now, I guess). People (including me) evidently
> crave this low, iron-level control, while at the same time mostly try to
> dodge writing any software in languages
Yeah +1 on waiting/asking/expecting CMOV to be properly utilized by
Hotspot, instead of trying to target the instruction ourselves. This is
all more of a curiosity / exploration. I am curious whether "branchless
binary search" is something Arrays.binarySearch already does / compiles
to. Even in
On Thu, Jul 27, 2023 at 9:19 AM Uwe Schindler wrote:
See Shipilevs blog:
> https://shipilev.net/jvm/anatomy-quarks/30-conditional-moves/
>
Really interesting! This is an awesome, quick explanation of the tradeoff
CMOV is making (pre-computing both paths) vs branching (have to predict,
with
On Thu, Jul 27, 2023 at 8:44 AM Uwe Schindler wrote:
> Hi Mike,
>
> actually Hotspot is using CMOV. Some nodes after bytecode analysis are
> converted to CMoveNode and it has implementations to generate machine code
> (as far as i see) for x86, s390 and arm.
>
> The generic code is here:
>
Interesting coincidence, I'm currently working on a learned index on sorted
keys that can advantageously replace binary search.
It is very compact (additional space of 2% of the sorted key array, e.g.
40KB for 200MB of keys), and it is between 2x to 3x faster than binary
search for the
> Actually this is exactly the same for Java:
>
Yup, I know (we all know by now, I guess). People (including me) evidently
crave this low, iron-level control, while at the same time mostly try to
dodge writing any software in languages that are designed to be close to
the hardware. There is a
Actually this is exactly the same for Java: You can try whatever you
want, the outcome of the dynamic optimization applied by various dynamic
building blocks (Java bytecode, Java/Hotspot version, command line
parameters, hardware CPU, virtualization) is not predictable and any
change anywhere
> Specifically, one of the fascinating Tantivy optimizations is the
> branchless binary search: https://quickwit.io/blog/search-a-sorted-block.
>
This is an interesting post, thanks for sharing, Mike. I remember when
people did such low-level tricks frequently (but on much simpler processors
and
gt; in-memory skip list structure (versus Lucene's on-disk (memory-mapped, by
>> default) multi-layer skip list) -- see the above blog post.
>>
>> This made me wonder: does javac's hotspot compiler use CMOVcc? I see javac
>> bug fixes like https://github.com/openjdk/mobile/
t) --
see the above blog post.
This made me wonder: does javac's hotspot compiler use CMOVcc? I see
javac bug fixes like https://github.com/openjdk/mobile/commit/a03e9220
which seems to imply C2 does in fact compile to CMOVcc sometimes. So
then I wondered whether a branchless binary search in Java
sometimes. So then I
wondered whether a branchless binary search in Java is a possibility? Has
anyone played with this?
Before Robert gets too upset :) Even if we could build such a thing, the
right place for such optimizations is likely the JDK itself (see the
similar discussion about
14 matches
Mail list logo
