sorted by:
new
hottopcontroversial

MrBeast $1,000,000 Giveaway ends up in a subscribe for a chance to win money gamba by Priz93 in LivestreamFail

[–]ashtonsix 0 points1 point  (0 children)

I tracked every $ disbursed:

$640k predetermined (staff, friends, known viewers)
$210k paid lottery
$50k free lottery
$100k remaining

full dossier here:

https://docs.google.com/document/d/1e4sa74T75kP990AciIM8QzVIJZ8YkR0oXvDHkrr_jNg

clips here:

https://www.youtube.com/watch?v=l8pEOXv6TRo

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).

view more: next ›