https://pvk.ca/Blog/2024/11/22/vpternlog-ternary-isnt-50-percent/

Paul Khuong: some Lisp

  * Blog
  * Archives
  * RSS


[                    ]
VPTERNLOG: when three is 100% more than two

Nov 22nd, 2024 | Comments

Like many, when I first saw VPTERNLOG, my reaction was "\(\log_2(3) \
approx 1.58\) is a nice reduction in depth, but my code mostly
doesn't have super deep reductions."

A little bit of thinking reveals a big win at smaller (reasonable)
scales: a binary operator takes two values and outputs one, while a
ternary operator takes three and outputs one. In a reduction, each
application of the binary operator decrements the number of values by
\(2 - 1 = 1\), but each application of the ternary operator
decrements it by \(3 - 1 = 2\)!

We thus need half as many ternary operations to reduce a given number
of bitvectors, compared to binary operations... and it's not like the
throughput (or latency for that matter) is worse. Plus it's hard to
be more orthogonal than a lookup table.

Cute lightweight instruction, two thumbs up!

Text authored by Paul Khuong Nov 22nd, 2024

<< Fixing the hashing in "Hashing modulo a-equivalence"

Comments

Please enable JavaScript to view the comments powered by Disqus.

Website copyright (c) 2024 - Paul Khuong | Powered by Octopress |
Themed with Konigspress