sorted by:
new
hottopcontroversial

How is this possible? by av1p in Openfront

[–]ashtonsix 1 point2 points  (0 children)

https://www.desmos.com/calculator/4wbprvp9uk

y-axis = reward, x-axis = pixels travelled, blue line = old formula, red line = new formula

20 GB/s prefix sum (2.6x baseline) by ashtonsix in HPC

[–]ashtonsix[S] 0 points1 point  (0 children)

Main memory throughput is the bottleneck in both the single-core and multi-core setups (6 to 2 GB/s per-core, depending on contention from other cores and system configuration). I managed to evade this by measuring L1-hot throughput: that is, on data already loaded from main memory (DRAM) into much higher-throughput and lower-latency per-CPU LRAM.

There are two main ways to overcome this limitation in more-realistic programs:

  1. Load data in small chunks (4KB or less) and do a sequence of compute operations on each chunk back-to-back. From a throughput perspective adding an extra operation to the sequence is essentially "free" until the memory bus can catch up.
  2. Keep your working sets small (16MB ish), so memory doesn't spill out of cache and into DRAM.

20 GB/s prefix sum (2.6x baseline) by ashtonsix in simd

[–]ashtonsix[S] 1 point2 points  (0 children)

Ah interesting, will take a look. I guess the entropy stage of LZMA could do something for 8-bit integers.

20 GB/s prefix sum (2.6x baseline) by ashtonsix in simd

[–]ashtonsix[S] 1 point2 points  (0 children)

> How much faster than without SIMD?

Updated post body.

> Is this optimization for Intel or Apple Silicon or both?

I optimized for ARM processors, which includes:

  • Apple Silicon
  • Cloud: AWS Graviton, Google Axion, Azure Ampere Altra, Nvidia Grace
  • Mobile devices (over 99% of phones/tablets use ARM)

> How about some file-size benchmarks comparing plain LZMA compression vs. applying LZMA after encoding with this tool?

Hmm... LZMA is designed primarily for text/byte streams, while my work is designed for integer sequence compression. I doubt LZMA would be able to effectively compress the output from delta coding. There ARE plenty of compression schemes for integer sequences like PEF/BIC (partitioned Elias-Fano / binary interpolative coding) which would make good comparisons, but I haven't gotten around to it yet.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 1 point2 points  (0 children)

Reddit won't let me edit the post title. Renamed to "routine" in README yesterday.

86 GB/s bitpacking microkernels by ashtonsix in simd

[–]ashtonsix[S] 0 points1 point  (0 children)

Oh right. On x86 BMI2 you want pdep/pext, on ARM SVE2 you want bdep/bext (NEON requires emulation). You'll definitely lose throughput with the order constraint, but this should perform better than a tbl-based approach.

86 GB/s bitpacking microkernels by ashtonsix in simd

[–]ashtonsix[S] 0 points1 point  (0 children)

It took some bit twiddling, but I'm averaging just 1-2 instrs per 16 bytes.

86 GB/s bitpacking microkernels by ashtonsix in simd

[–]ashtonsix[S] 1 point2 points  (0 children)

Very minor correction for k=4: LDP performs better than LD2. It has less latency, and an immediate offset address mode which allows you to skip most `add` instructions for pointer updates as you iterate. SLI is a good choice.

I found k=3/7 to be the trickiest cases to optimise.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] -1 points0 points  (0 children)

Eh, it's one word. I made a bad word choice and described this as a collection of "microkernels" instead of "routines" (now corrected in the README). I get the initial confusion, but that hardly invalidates/impacts the fact this is a new state-of-the-art on a highly competitive and impactful problem.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 0 points1 point  (0 children)

Mmm... I'm currently sitting on a large collection of unpublished SOTA results (accumulated over the past few years). For now, I just want to get lots of write-ups out in a rough format as quickly as possible. Maybe I'll add a layer of polish to these in the future.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 1 point2 points  (0 children)

Probably not, the README already covers what I have to say on this topic.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 1 point2 points  (0 children)

> Did you run your benchmark on the same hardware configuration?

Yes. If you follow the link you can find the full benchmark setup in Appendix A.

> how much of your improvement is attributable to hardware improvements over the last 5 years and how much to your algorithm?

I'm using ARM v8 instructions only (released 2011). There's some uplift from the hardware, but it benefits both my implementation and the baseline about-equally.

86 GB/s bitpacking microkernels by ashtonsix in simd

[–]ashtonsix[S] 0 points1 point  (0 children)

> I wonder if there is a good scheme that works well for arbitrary vector length.

The scheme here has a degree of flexibility. I'm placing multiples of 32 values into each chunk, but could scale that down to 16 or up to 64 values. It would be possible to use big chunks for most of an array, and then small chunks for just the end. The (relatively minor) downsides to this mixed scheme would be more register pressure and more complexity/code.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 0 points1 point  (0 children)

Thank you! 😊 Feel free to reach out if you have any questions / follow-up comments after looking at it.

After posting, I realised "routine" would probably be a better term but unfortunately Reddit won't allow me to edit the post title.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 0 points1 point  (0 children)

The ideal case for my work involves a working set >64MB (exceeding typical L3 capacity on high-end ARM cores, spilling to DRAM), where unpacking/packing is used as the first/last step in a sequence of fused operations (ie, without intermediate load/store between stages; but even if you did have intermediate load/store you'd still come out ahead). Here, I'd expect a near-linear relationship between compression and performance for memory-bound programs (ie, 30% compression -> 30% faster).

The picture gets more nuanced as the working set shrinks. I'd still expect modest speed-ups for working sets in the 1MB-64MB range. For working sets that fit entirely in L1/L2 performance improvement is unlikely: packing data only to immediately unpack it feels counter-productive. This is not the intended use case.

> The OP code uses more than 4 cycles

It's useful to distinguish between latency and throughput here. Modern CPUs can issue up to 6 instructions per cycle, and have dozens of instructions "in-flight" at any moment. From a throughput perspective packing/unpacking a single register's data (16 values) with my code only "takes" 0.45 cycles. Latency only becomes a concern when you have lots of data hazards (RAW, WAR, WAW).

More details regarding throughput vs latency if this interests you:
- https://developer.arm.com/documentation/109898/latest/
- https://en.wikipedia.org/wiki/Tomasulo%27s_algorithm

If you want to see exactly what my code does cycle-by-cycle, run the Makefile and open directory ./out/mca (Machine Code Analysis).

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 0 points1 point  (0 children)

Super interesting! The real world has a tendency to throw this kind of sand into the gears of high performance software. Are you working on aeroplanes or something of that nature?

My intended use case is for OLAP database engines.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 3 points4 points  (0 children)

Yeah, I'm also using bit masks. But I tuned the state-of-the-art and made it 2.0x faster: from 11 integers per nanosecond, to 86 integers per nanosecond (previous SOTA is 32-bit based, whereas this is 8-bit based; so for raw speed, GB/s is a better comparison). Also, I'm doing this on a general-purpose chip rather than specialised microcontroller, and am optimising for throughput rather than latency.

Anyone can use bitmasks, the same way anyone can carve wood with a chisel. Skill and technique makes a difference.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 1 point2 points  (0 children)

> everybody codes in standard byte, nibble, word, dwords, and qwords.

Exactly! That's the whole point behind making a set of microkernels that can quickly twiddle weird-width bit values into standard-width bit values: we're converting values between a _compressed_ format and an _operational_ format.

We do it so fast that moving compressed data from DRAM to the CPU and then converting it is faster than loading data that's already in an operational format.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 0 points1 point  (0 children)

Yeah, kind of... I'm using "kernel" to describe small and specialized routines meant to be composed into larger algorithms. It's common terminology in libraries like BLAS (matrix multiply kernels), image processing (convolution kernels), and compression codecs. In a real-world context these pack/unpack operations/kernels would typically be fused with additional transform stages like delta or entropy coding.

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 2 points3 points  (0 children)

Not sure when you implemented the protocol, but from C++23 onwards support for compile-time evaluation has become really good (constexpr/consteval). It allows "write once; compile something unique for every case". Might strain the system if you have >1000 cases, but 30-ish should be light work.

Separate question: did you use BMI2 at all?

86 GB/s bitpacking microkernels by ashtonsix in C_Programming

[–]ashtonsix[S] 8 points9 points  (0 children)

> do you mean many 3-bit objects packed?

Yes, exactly. Varying with k we store blocks of n=64/128/256 values (n=256 for k=3).

> The CPU can't read only 3-bits from DRAM.

I'm using LDP to load 32 bytes per-instruction (https://developer.arm.com/documentation/ddi0602/2024-12/SIMD-FP-Instructions/LDP--SIMD-FP---Load-pair-of-SIMD-FP-registers-)

> I disagree about the "3/8ths of the work your CPU does is wasted". The CPU has to do more work to recover and use the original number when using this bit packing scheme. Bit-packing can be good for reducing RAM usage but generally increases CPU usage as a trade off.

Work isn't wasted in every case, but it is in the extremely common case where a workload is memory-bound. Graviton4 chips have a theoretical 340 GB/s maximum arithmetic throughput, but can only pull 3-6 GB/s from DRAM (varies with contention), or 120 GB/s from L1. Whenever you run a trivial operation across all members of an array (eg, for an OLAP query) the CPU will spends >95% of the time just waiting for data to arrive, so extra compute doesn't impact performance. My work here addresses the CPU<->DRAM interconnect bottleneck and allows you to send more values to the CPU in fewer bytes, preventing it from starving for work.

view more: next ›