Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Beating the L1 cache with value speculation (2021)

mazzo.li

Post reply on HN
Print view View original

11–20 of 87 posts

Re: Beating the L1 cache with value speculation (2021)

#11

Post by gus_massa »

IshKebab wrote: post #6

Neat trick. Though it seems unlikely to be very useful in practice. How often are you going to know the probably value of a pointer without knowing the actual value? I would guess it's pretty rare. Interesting anyway!

It's possible to have a "sparse" matrixes where most of the values are 0 and only a few are not null. So you can guess 0 and cross your fingers.

(There are libraries that implement sparse matrixes in a more memory efficient way. I needed them for a program in Python, but I'm not an expert in Python. I found a few ways, but they are only useful for big matrixes with very few coeficients and have other restrictions to get an improved speed. I finaly gave up and used a normal np matrixes.)

Re: Beating the L1 cache with value speculation (2021)

#12

Post by bell-cot »

IshKebab wrote: post #6

Neat trick. Though it seems unlikely to be very useful in practice. How often are you going to know the probably value of a pointer without knowing the actual value? I would guess it's pretty rare. Interesting anyway!

Bigger-picture, this method amounts to manually assisted speculative execution. And it's not about knowing the not-yet-loaded value, but about knowing what will (very likely) happen as a consequence of that value.

Re: Beating the L1 cache with value speculation (2021)

#14

Post by dmoy »

IshKebab wrote: post #6

Neat trick. Though it seems unlikely to be very useful in practice. How often are you going to know the probably value of a pointer without knowing the actual value? I would guess it's pretty rare. Interesting anyway!

Well in the articles case, it's the linked list `next` pointers:

https://mazzo.li/posts/value-speculation.html#value-speculat...

In a happy case, those will be laid out sequentially in memory so you can guess the value of the pointer easily.

(That said your comment still stands, since using linked lists in the first place is much more rare). But I suppose there's probably a lot of other domains where you might have a performance critical loop where some hacky guessing might work.

Re: Beating the L1 cache with value speculation (2021)

#17

Post by account42 »

dmoy wrote: post #14
IshKebab wrote: post #6

Neat trick. Though it seems unlikely to be very useful in practice. How often are you going to know the probably value of a pointer without knowing the actual value? I would guess it's pretty rare. Interesting anyway!

Well in the articles case, it's the linked list `next` pointers: https://mazzo.li/posts/value-speculation.html#value-speculat... In a happy case, those will be laid out sequentially in memory so you can guess the value of the pointer easily. (That said your comment still stands, since using linked lists in the first place is much more rare). But I suppose there's probably a lot of other domains where you might have a…

Not only are linked lists rare, they are also mainly useful exactly in situations where you cannot guarantee a (even mostly) linear allocation order.

Re: Beating the L1 cache with value speculation (2021)

#18

Post by gpderetta »

mnw21cam wrote: post #5

The article states that the CPU has a limit of 4 instructions per cycle, but the sum2 method issues 5 instructions per cycle. Presumably one of them (maybe the increment) is trivial enough to be executed as a fifth instruction.

some nominally 4-wide intel cpus can execute 5 or 6 instructions per cycle when macrofused. For example a cmp and a conditional jXX can be macrofused.

Re: Beating the L1 cache with value speculation (2021)

#19

Post by gpderetta »

IshKebab wrote: post #6

Neat trick. Though it seems unlikely to be very useful in practice. How often are you going to know the probably value of a pointer without knowing the actual value? I would guess it's pretty rare. Interesting anyway!

In principle a compiler via JIT or PGO could do this optimization automatically.

Re: Beating the L1 cache with value speculation (2021)

#20

Post by gpderetta »

account42 wrote: post #17
dmoy wrote: post #14

Earlier quoted context omitted.

Well in the articles case, it's the linked list `next` pointers: https://mazzo.li/posts/value-speculation.html#value-speculat... In a happy case, those will be laid out sequentially in memory so you can guess the value of the pointer easily. (That said your comment still stands, since using linked lists in the first place is much more rare). But I suppose there's probably a lot of other domains where you might have a…

Not only are linked lists rare, they are also mainly useful exactly in situations where you cannot guarantee a (even mostly) linear allocation order.

the optimization could be vaguely interesting if you are implementing a lisp (or some other list heavy language) and don't want to perform too aggressive non-local optimizations to optimize the layout of lists.
Post reply on HN