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

How to pack ternary numbers in 8-bit bytes

compilade.net

Post reply on HN
Print view View original

21–30 of 55 posts

Re: How to pack ternary numbers in 8-bit bytes

#21

Post by lioeters »

Amusing that the link to an article on ternary numbers was posted by Mr Triplett. (:

The article is well-written and illustrated. The technique described is used in llama.cpp for running language models like BitNet b1.58 whose weights are stored as ternary types.

> ..in which every single parameter (or weight) of the LLM is ternary {-1, 0, 1}

> significantly more cost-effective in terms of latency, memory, throughput, and energy consumption

The original paper on this technique was published in Feb 2024. (Also linked from the article)

The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits - https://arxiv.org/abs/2402.17764

However, since then there have only been a few other models using ternary weights. I get the impression that there are factors not considered in the paper which make it less practical than it seemed.

Re: How to pack ternary numbers in 8-bit bytes

#22

Post by akoboldfrying »

Diggsey wrote: post #14

How does this packing/unpacking scheme compare to just using a lookup table?

A 256x3=768-byte lookup table will almost certainly be faster on a CPU. It will fit easily in L1 cache, and can extract 3 bytes at a time.

Ironically, x86 has an instruction, XLATB, that does almost exactly this (looking up a byte in a 256-byte table) -- but using it is actually slower than using an equivalent MOVZX RAX,AL; MOV AL,[RBX+RAX] sequence on modern CPUs.

Re: How to pack ternary numbers in 8-bit bytes

#23

Post by StilesCrisis »

marginalia_nu wrote: post #8
Joker_vD wrote: post #7

> Fixed point numbers to the rescue! > a diagram that shows that dividing 0x7F (127) by 243 and then multiplying by 256 results in 0x86 (134) > Tada! How... how does that help with anything? > Now digits can be easily extracted from the top two bits of the resulting 10-bit number when multiplying this 8-bit byte by 3. What? Why? How? This is supposed to be the most insightful part of the post, and it's literally just…

If it's any consolation, I spent like two years of my life immersed in this field[1] and can still recite powers of three in the same way most nerds can only tell you powers of two, yet I still can't follow this floating point black magic. [1] behold my misspent youth: https://tunguska.sf.net/

Fixed point! Not floating. That's the whole trick.

Re: How to pack ternary numbers in 8-bit bytes

#24

Post by akoboldfrying »

zephen wrote: post #17
Diggsey wrote: post #14

How does this packing/unpacking scheme compare to just using a lookup table?

I was wondering the same thing. Obviously, it partly depends on the implementation machine, how big a hole the tables blow in your cache, how fast the multiplies are, etc. But it probably also hugely depends on the format that you want your trits in. If you use them unpacked, e.g. one trit per byte, then even if you're using tables, you still have to do a lot of manipulation (e.g. either shifting and oring, or having…

You can have a single 3x256=768-byte table -- just multiply the input byte by 3 to get the offset into the table, and read out the 3 trits (1 trit per byte) beginning at that offset.

ETA: If you're prepared to waste a byte per entry so that entries are 4 bytes wide, on x86 you can use effective address calculation to do the multiplication for you, letting you decode 3 trits in 1 CPU instruction:

    MOV EAX,[RBX+RCX*4]

Re: How to pack ternary numbers in 8-bit bytes

#25

Post by marginalia_nu »

StilesCrisis wrote: post #23
marginalia_nu wrote: post #8

Earlier quoted context omitted.

If it's any consolation, I spent like two years of my life immersed in this field[1] and can still recite powers of three in the same way most nerds can only tell you powers of two, yet I still can't follow this floating point black magic. [1] behold my misspent youth: https://tunguska.sf.net/

Fixed point! Not floating. That's the whole trick.

Ah, then it makes at least some sense.

Re: How to pack ternary numbers in 8-bit bytes

#27

Post by mcherm »

taneq wrote: post #15
Imustaskforhelp wrote: post #10

Earlier quoted context omitted.

Arturo[0] language supports true,false and maybe. I really liked that idea actually, worth mentioning here. so valid arturo code can be like (picked from their in-a-nutshell documentation) i1: true i2: false i3: maybe [0]: https://arturo-lang.io/documentation/in-a-nutshell

Everyone hates null but (in database land, and arguably in other programming) it just means “no data.” (As an aside, I found the characterisation of null as being a “billion dollar mistake” to be unfair. Those who don’t acknowledge null are doomed to reimplement it, probably poorly, or to have the unknowns in their logic remain unknown unknowns.)

The "mistake" was not in providing a way to represent "no data", it was in providing no way to represent "this definitely HAS" data.

Languages that correct the problem have two separate types (eg: Foo & Option) meaning "definitely a Foo" and "a Foo but it might have no data". Java just has Foo, meaning "a Foo but it might have no data" but no way to represent "definitely a Foo".

Re: How to pack ternary numbers in 8-bit bytes

#29

Post by zephen »

akoboldfrying wrote: post #24
zephen wrote: post #17

Earlier quoted context omitted.

I was wondering the same thing. Obviously, it partly depends on the implementation machine, how big a hole the tables blow in your cache, how fast the multiplies are, etc. But it probably also hugely depends on the format that you want your trits in. If you use them unpacked, e.g. one trit per byte, then even if you're using tables, you still have to do a lot of manipulation (e.g. either shifting and oring, or having…

You can have a single 3x256=768-byte table -- just multiply the input byte by 3 to get the offset into the table, and read out the 3 trits (1 trit per byte) beginning at that offset. ETA: If you're prepared to waste a byte per entry so that entries are 4 bytes wide, on x86 you can use effective address calculation to do the multiplication for you, letting you decode 3 trits in 1 CPU instruction: MOV EAX,[RBX+RCX*4]

There are 5 trits.

In any case, if there were 3 trits, I'm not sure what the practical difference between a single table you describe and 3 different 256 byte tables, again depending on the architecture.

Yes a single table would have better cache effects for a single read, but presumably? you're doing a lot of reads in an unpacking phase.

Re: How to pack ternary numbers in 8-bit bytes

#30

Post by anagnost »

Razengan wrote: post #19

I was actually mucking with ChatGPT about possible "post-binary" architectures. I ended up feeling that ternary is just icky, because the "middle value" doesn't have an "opposite" Maybe we should do what quaternions did to complex numbers and just jump from 2 to 4: Quaternary CPUs I couldn't understand half of the words it spat out but it turns out that using pairs of "quits" as the atomic computation unit to represe…

I have the opposite feeling: balanced ternary naturally removes the ickiness of twos-complement arithmetic and the unbalanced MIN_INT.
Post reply on HN