Compilade's Blog

Compilade's BlogHow to pack ternary numbers in 8-bit byteshttps://compilade.net/blog/ternary-packingPacking ternary numbers with efficient SIMD-friendly unpacking on binary computers<main morss_own_score="2.8520345252774355" morss_score="69.7178313565915"> <h1>How to pack ternary numbers in 8-bit bytes</h1> with efficient SIMD-friendly unpacking <hr> Published: <time>2024-06-26</time> There are 3 possible values in a digit of a ternary number. 3 possible values, which could actually be anything. <text>-1</text> <text>0</text> <text>1</text> <text>0</text> <text>1</text> <text>2</text> I've been recently nerd-sniped<a href="https://compilade.net/blog/ternary-packing#fn:1">1</a> into trying to pack the ternary weights of <a href="https://arxiv.org/abs/2402.17764">BitNet b1.58</a> into something close to that theoretical ideal of <code>log(3) / log(2)</code> bits<a href="https://compilade.net/blog/ternary-packing#fn:2">2</a> per ternary digit. I'll be calling a "ternary digit" a "trit", like a "binary digit" is called a "bit". <h2>Block size</h2> Since the goal of this is to allow fast parallel unpacking, blocks of trits can't be infinitely big. A small "block" size needs to be found, ideally one which is both efficient with information density and which is convenient on current hardware. To find a good block size, we'll need to find a power of 3 for which the next power of 2 is very close. <table> <thead> <tr> <th>trits</th> <th>3trits</th> <th>bits</th> <th>2bits</th> <th>bits per trit</th> </tr> </thead> <tbody> <tr> <td>1</td> <td>3</td> <td>2</td> <td>4</td> <td>2</td> </tr> <tr> <td>2</td> <td>9</td> <td>4</td> <td>16</td> <td>2</td> </tr> <tr> <td>3</td> <td>27</td> <td>5</td> <td>32</td> <td>1.666...</td> </tr> <tr> <td>4</td> <td>81</td> <td>7</td> <td>128</td> <td>1.75</td> </tr> <tr> <td>5</td> <td>243</td> <td>8</td> <td>256</td> <td>1.6</td> </tr> </tbody> </table> It's very fortunate that 5 trits fit quite tight into 8 bits at <code>1.6 bits</code> per trit. When compared to perfect packing, this is <code>99.06%</code> efficient. <h2>1.6 bits per trit</h2> The basic idea with this packing scheme is simply to make a number out of the ternary digits. <pre><code>def pack_number(digits: list[int], base: int) -> int: number = 0 for digit in digits: assert digit < base number = number * base number = number + digit return number </code></pre> Packing trits into bytes should be similar enough. <h3>Fast multiplication unpacking</h3> While repeated remainder and divisions can be used to extract the digits of a number, the problem with divisions and modulo is that they are not usually supported on integers in <abbr title="Single Instruction Multiple Data">SIMD</abbr> programming. A way around this is obviously to view numbers differently. Would it be nice if instead of extracting the least significant digit with modulo, we could extract the most significant digit with a multiplication? Fixed point numbers to the rescue! <text>0x7F.</text> <text>11201.</text> <text>.11201</text> <text>0x0.86</text> <text>0x86.</text> <text>same number</text> <text>divide by 243</text> <text>same number, round up</text> <text>multiply by 256</text> Tada! 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. This is much more convenient than modulo when unpacking with <abbr title="Single Instruction Multiple Data">SIMD</abbr>. The only place where there are divisions in this scheme when packing trits into bytes. This assumes that packing is done less often than unpacking, which is very true in the context of <abbr title="Large Language Model">LLM</abbr> weights. <pre><code># Take a list of values in -1, 0, 1 and pack them in bytes def pack_trits(digits: list[int]) -> bytearray: assert len(digits) % 5 == 0 # padding isn't handled here n_bytes = len(digits) // 5 packed = bytearray() for i in range(n_bytes): b = 0 for j in range(5): digit = digits[5*i + j] digit = max(-1, min(digit, 1)) # clamp between -1 and 1 digit += 1 # from -1, 0, 1 to 0, 1, 2 b *= 3 b += digit b = ((b * 256) + (243 - 1)) // 243 packed.append(b) return packed </code></pre> The relevant interesting line is this one: <pre><code> b = ((b * 256) + (243 - 1)) // 243 </code></pre> It does what is depicted in the diagram above, but multiplication is done first because these are integer operations. Doing a ceiling division here is necessary to cancel the off-by-one error from truncating when extracting digits later. To unpack without using the modulo operator: <pre><code>def unpack_trits(packed: bytes) -> list[int]: trits: list[int] = [] for byte in packed: b = byte for i in range(5): b = b * 3 trit = b >> 8 trits.append(trit - 1) # 0, 1, 2 => -1, 0, 1 b = b & 0xFF return trits </code></pre> To convince myself that this works, I wrote a C program checking that this really is lossless: <pre><code>#include <stdint.h> #include <stdio.h> #include <string.h> int main(void) { char s1[6] = {0}; char s2[6] = {0}; for (uint8_t i = 0; i < 243; ++i) { uint8_t n = i; // Get the number representation in base 3 // by repeatedly extracting the least significant digit with modulo for (int j = 5; j-- > 0;) { s1[j] = (n % 3) + '0'; n /= 3; } // Turn that number into a fixed-point number smaller than 1 uint8_t q = (((uint16_t) i) * 256 + (243 - 1)) / 243; // This extracts the most significant digit first for (int j = 0; j < 5; ++j) { uint16_t m = q * 3; s2[j] = (m >> 8) + '0'; q = m & 0xFF; } printf("%s, %s: %s\n", s1, s2, strcmp(s1, s2) == 0 ? "\033[1;32mPASS\033[0m" : "\033[1;31mFAIL\033[0m"); } return 0; } </code></pre> Compile and run with: <pre><code>$ gcc ternary-packing.c -o ternary-packing $ ./ternary-packing </code></pre> And I'm getting <code>PASS</code> for each of the 243 ternary numbers which fit in 8 bits. And this is the technique used in the ternary types in <code>llama.cpp</code> for TriLMs and BitNet b1.58, for which the pull request is <a href="https://github.com/ggml-org/llama.cpp/pull/8151">https://github.com/ggml-org/llama.cpp/pull/8151</a>, with <abbr title="Single Instruction Multiple Data">SIMD</abbr> implementations for both AVX2 and ARM NEON. <hr> <ol> <li> obviously referring to <a href="https://xkcd.com/356/">https://xkcd.com/356/</a>, but the initial motivation actually started from <a href="https://github.com/ggml-org/llama.cpp/pull/7931#discussion_r1640265346">this review comment I posted</a> on the initial BitNet b1.58 pull-request for <code>llama.cpp</code> <a href="https://compilade.net/blog/ternary-packing#fnref:1" title="Jump back to footnote 1 in the text">↩</a> </li> <li> <code>log(3) / log(2)</code> is also known as <code>1.584962500721156</code>. <a href="https://compilade.net/blog/ternary-packing#fnref:2" title="Jump back to footnote 2 in the text">↩</a> </li> </ol> </main> Wed, 26 Jun 2024 00:00:00 UTCWhy Python over Lua over shell scripts to build my bloghttps://compilade.net/blog/why-python-ssgThe best way I found to completely understand how to use a static site generator was to build my own. I now understand at least one!<main morss_own_score="2.698645598194131" morss_score="163.375244105817"> <h1>Why Python over Lua over shell scripts to build my blog</h1> The best way I found to completely understand how to use a static site generator was to build my own. I now understand at least one! <hr> Published: <time>2023-10-22</time> It's very common for the first post in a technical blog to be about how the site was built. I'm not making an exception here; this is an explanation of my many attempts at making a static site generator (and why I ended up using Python). <h2>A little history</h2> Before I started working on building my own static site generator, but after I first got this domain name, I already had some kind of Fossil repositories, so <a href="https://fossil.compilade.net/compilade/index">I used one as a home page</a> for a while. <a href="https://fossil-scm.org/">Fossil</a> is nice and all, but since it's mainly a version control system, there are a bunch of pages in the web interface that are not necessary for a personal website (help pages, logins, etc.), and some features are missing (like <a href="https://sitemaps.org/protocol.html"><code>sitemap.xml</code></a> generation). Even if Fossil's source code is relatively easy to extend, removing parts of the web interface was a big enough change that it made me consider "easier" ways instead. I figured that my preferred way would involve building a static site from Markdown files and some kind of script. <h2>The POSIX attempt</h2> <a href="https://git.compilade.net/fch/blog/src/commit/b055a1690a16896af7784a8dc922ce5a0f1211ab/build.sh">My initial attempt</a> used a POSIX shell script that called Pandoc with some custom <a href="https://pandoc.org/lua-filters.html">Lua filters</a>. At first, the script was simple enough, but when I got around to generate the blog's <a href="https://validator.w3.org/feed/docs/atom.html">Atom</a> feed and the page which lists the blog posts (which both share lots of information), I really felt like I needed arrays and/or hash tables, neither of which can be straightforwardly done in POSIX shell scripts (and no, a big string of many substrings separated by rare control characters doesn't count). At that point, I probably should simply have assumed that I could use all of <code>bash</code>'s features instead of limiting my script to POSIX compatibility. But no, I made a POSIX shell script, so that meant a lot of calls to <code>sed</code> and <code>tr</code> that could have been avoided with some <code>bash</code> variable expansion magic. Anyway, I was ready to rewrite it all in another scripting language. I still wanted to use some kind of "small" programming language to minimize the build dependencies of my site. <h2>Lua, simpler?</h2> I was already using Lua filters with Pandoc, so it wasn't much of a leap to also use Lua for the rest of the build script. So <a href="https://git.compilade.net/fch/blog/src/branch/main/build.lua">I rewrote the script in Lua</a>, including some kind of custom command-line arguments parser (because Lua doesn't have something like <a href="https://manpages.debian.org/bookworm/bash/bash.1.en.html#getopts"><code>getopts</code></a> built-in). Apart from args parsing, the Lua script was much cleaner than its shell script counterpart. I could finally use lists and tables instead of putting everything in strings! And I could even include the build script as a module to access my helper functions in the Lua filters passed to Pandoc! (which strangely did not add measurable overhead) <h3>Pandoc troubles</h3> <a href="https://pandoc.org/">Pandoc</a> is very good software and is extremely useful. But Pandoc is also a bit slow to run (<code>20 ms</code> on my machine<a href="https://compilade.net/blog/why-python-ssg#fn:my-machine">1</a>, compared to <code>2 ms</code> for lowdown), and this compounds with the fact that one Pandoc call can only process a single file. This means the minimum time it would take to run Pandoc on only 5 files would be <code>100 ms</code>! And this excludes the additional time it takes when Pandoc has to do syntax highlighting (around <code>300 ms</code> per file)! So I made <a href="https://git.compilade.net/fch/blog/src/commit/50d4163b1020d39f66a8008cf3dd8a840360b1c9/build.lua#L255">some one-liner abomination to run Pandoc in parallel</a> to lessen the effect of Pandoc's relatively slow run time. I hope you like scrolling sideways, because this line is waaaaaay too long (and somewhat of an unmaintainable mess) : <pre><code>os.execute("find "..escape(dir).." -maxdepth 1 -iname "..escape(glob)..(exclude_pat and " '!' -iname "..escape(exclude_pat) or "").." -print0 | sed -z -E -e "..escape([[s,^(.*/)?(\.?[^./]*?)\.[^/]*$,\2,]]).." | xargs -0 -P 4 -I '{}'"..(verbose and " -t" or "").." pandoc"..(pandoc_args and " "..table.concat(escaped_pandoc_args, " ") or "").." "..escape("--output="..out.."/{}."..out_ext:gsub("^%.","")).." "..escape(dir.."/{}."..ext)) </code></pre> But it somehow felt necessary for performance. <h4>Syntax highlighting</h4> The syntax highlighting of Pandoc also is not ideal; it's a bit slow and it does not support all the syntaxes I want to use. While it can highlight the syntax of most programming languages, (at the time of writing) it cannot highlight shell sessions out-of-the-box<a href="https://compilade.net/blog/why-python-ssg#fn:shell-session-hl">2</a>! <pre><code>$ echo "Hello world" Hello world </code></pre> See? This works because I'm using <a href="https://pygments.org/">Pygments</a>. The standalone <code>pygmentize</code> tool also has a slow startup speed, but at least it supports all the syntaxes I'm interested in using. I've looked at other syntax highlighters before settling on Pygments. One of them was <code>chroma</code>, but its command-line tool had no way to safely get a language name without also possibly interpreting it as a file name<a href="https://compilade.net/blog/why-python-ssg#fn:chroma-lang-file">3</a>. At one point I even considered not using syntax highlighting at all for my website to make the build go faster. <h4>Pandoc Templates</h4> A cool thing with Pandoc is that it has its own relatively simple syntax for templates<a href="https://compilade.net/blog/why-python-ssg#fn:pandoc-template-syntax">4</a>. It seemed ideal for a static site generator! But then I realized that the default Pandoc templates (which I was (at the time) using as a base for my own custom templates) are not in the public domain; they are licensed under GPLv2+ and BSD3 (see <a href="https://github.com/jgm/pandoc-templates">https://github.com/jgm/pandoc-templates</a>). For some reason, I wanted to be able to use the license of my choosing on the source of my website. And I didn't want to have to include a copy of the BSD3 license of another project<a href="https://compilade.net/blog/why-python-ssg#fn:pandoc-template-bsd3">5</a> only for the templates. That meant I had to start over (again) and build my own templates from scratch and avoid Pandoc and all of its niceties like Lua filters. <h3>No Pandoc?</h3> But I still wanted to run filters on the HTMLized Markdown of my site! Unfortunately (and predictably), Lua can't parse HTML without either using a library for XML (like <a href="https://github.com/lunarmodules/luaexpat"><code>luaexpat</code></a>) or parsing it on my own. Since I no longer wanted to use Pandoc for my site, Lua stopped having the advantage of already being a dependency, so this led me to search for a programming language with a bigger standard library. <h2>Python!</h2> I never really used Python seriously like this before. It's kind of enlightening that something I thought was so awful works so well. <h3>Slow startup</h3> What makes <code>pygmentize</code> start up slowly is Python's own startup speed (<code>23 ms</code> minimum on my machine). For comparison, both Lua and Perl start in <code>3 ms</code> on the same machine<a href="https://compilade.net/blog/why-python-ssg#fn:my-machine">1</a>. <pre><code>$ time python3 -c 'print("Hello world")' Hello world real 0m0.023s user 0m0.018s sys 0m0.004s $ time lua -e 'print("Hello world")' Hello world real 0m0.003s user 0m0.001s sys 0m0.002s $ time perl -e 'print("Hello world\n")' Hello world real 0m0.003s user 0m0.001s sys 0m0.002s </code></pre> And that's even after a few previous runs. A solution is to use Pygments directly from a Python script. That way, the Python interpreter is only started once, even if thousands of snippets need highlighting. Perhaps paradoxically, Python's slow startup speed can be an incentive to use Python, since anything else calling Python libraries is slower (unless you're using C or C++ and want to <a href="https://docs.python.org/3/extending/embedding.html">embed the Python interpreter</a> in your program). Remember, I want to use Pygments because it seems well-maintained and one of the best server-side syntax highlighter I found which can highlight shell sessions. <h3>Args parsing</h3> I was very pleasantly surprised to find out about the <a href="https://docs.python.org/3.10/library/argparse.html"><code>argparse</code></a> module in Python's standard library. It even makes the <code>--help</code> from the descriptions of each sub-commands and flags! It's much more concise than manually writing and structuring the <code>--help</code> output in shell scripts, and much easier than manually parsing the command-line arguments like I did in Lua. <h3>Filters</h3> Python's standard library natively supports XML<a href="https://compilade.net/blog/why-python-ssg#fn:python-xml">6</a>! But HTML is not XML. The solution I'm happy with for now is to build XHTML pages (which are valid XML) and then run what I'm calling "XML filters" on those pages. This makes it "easy" to make every internal link relative and to make them use the final location of their destination. It also makes it relatively simple to clean up what is included in the Atom feed of the blog. For example, my posts include syntax highlighting for code snippets, but the spans and classes inserted by Pygments are useless in a feed since styling is mostly ignored by feed readers. So I made filters to remove all <code>class</code> attributes and all <code>span</code> elements for the included XHTML in the Atom feed. I'm not sure if there are other ways to do all of this, but I'm pretty happy with the versatility of XML. <h3>Type checking</h3> I vaguely knew that <a href="https://peps.python.org/pep-0484/">type annotations</a> were supported by Python, so I used them to make some of the function definitions clearer. But type annotations are ignored by the Python interpreter, so I looked for a static type checker. I found out about <a href="https://github.com/microsoft/pyright">Pyright</a>, and it's impressively useful once set up correctly. Static type checking in a scripting language is so nice, and it hugely helps with refactoring (which I've heard a lot, but which I first really experienced with this script because even after 2 rewrites, I still had many other ideas of things to change). <h2>You're looking at the result</h2> This is my site, and it's built from <a href="https://git.compilade.net/fch/compilade-pages/src/branch/main/build.py">this Python script</a>. All the programming languages I considered for my build script are (interpreted) scripting languages. Why? Because it felt simpler to avoid making a build script for my build script. The build script is evolving along with the site, so that means it changes as much or as little as I want, and only when I want it to change (unlike with static site generators like <a href="https://gohugo.io">Hugo</a>). And no need to avoid breaking changes, since I'm (or should be) the only user of my build script! Hopefully, I'll be writing more blog posts instead of shaving the yak. <hr> <ol> <li> For the record, my main machine is not that powerful compared to what's available nowadays. It's a low-power laptop whose processor is an <a href="https://www.intel.com/content/www/us/en/products/sku/185282/intel-core-m38100y-processor-4m-cache-up-to-3-40-ghz/specifications.html">Intel Core m3-8100Y</a>. <a href="https://compilade.net/blog/why-python-ssg#fnref:my-machine" title="Jump back to footnote 1 in the text">↩</a><a href="https://compilade.net/blog/why-python-ssg#fnref2:my-machine" title="Jump back to footnote 1 in the text">↩</a> </li> <li> It's still possible to use custom syntax definitions to highlight shell sessions in Pandoc, see <a href="https://github.com/jgm/skylighting/issues/67">https://github.com/jgm/skylighting/issues/67</a> <a href="https://compilade.net/blog/why-python-ssg#fnref:shell-session-hl" title="Jump back to footnote 2 in the text">↩</a> </li> <li> The only option of the <abbr title="Command-line interface">CLI</abbr> of <code>chroma</code> that can set the language to be highlighted (as desirable for snippets on a website) is <code>--lexer</code> (or <code>-l</code>). See <a href="https://github.com/alecthomas/chroma/blob/7eb0305e1b3b0d6af8aac735417a58c7322c932d/cmd/chroma/main.go#L53">the description of <code>chroma</code>'s lexer flag</a>. <a href="https://compilade.net/blog/why-python-ssg#fnref:chroma-lang-file" title="Jump back to footnote 3 in the text">↩</a> </li> <li> And that's even when assuming the dual licensing of <code>pandoc-templates</code> means either license can be used, but this is probably wrong since that project's README says it's under both licenses, so that would mean the safest way to use variations of the Pandoc templates would be to license everything (including my build script) under the GPLv2+ license, while also keeping the BSD3 license of <code>pandoc-templates</code>. Too many licenses to think about (and ways to make mistakes) in this case, so I'm glad I started from scratch to avoid being burdened by licenses I did not choose (even though I might end up using the GPL anyway). <a href="https://compilade.net/blog/why-python-ssg#fnref:pandoc-template-bsd3" title="Jump back to footnote 5 in the text">↩</a> </li> <li> I was very happy when I found out XML parsing and tree building are built into Python. <a href="https://docs.python.org/3/library/xml.html">https://docs.python.org/3/library/xml.html</a> <a href="https://compilade.net/blog/why-python-ssg#fnref:python-xml" title="Jump back to footnote 6 in the text">↩</a> </li> </ol> </main> Sun, 22 Oct 2023 00:00:00 UTC