Const-me

Hey, Katie. Just FYI, last week I paid $250 to your competitor after being unable to pass your identity verification. BTW, your web site didn’t even offer me an option to verify ID with a Paypal payment.

> the api and the different ways everything has to be fed for it leaves a lot to be desired

I think Microsoft fixed that in Windows Vista by providing a higher-level APIs on top of IOCP. See CreateThreadpoolIo, CloseThreadpoolIo, StartThreadpoolIo, and WaitForThreadpoolIoCallbacks WinAPI functions.

You’re describing an edge case. Generally speaking, memory is only reused after old objects are deallocated. And here’s the relevant quote from the OP’s post:

> Having all the intermediate calculations still available is helpful in the debugger

For performance critical code, you want to reuse L1D cache lines as much as possible. In many cases, allocation of a new immutable object boils down to malloc(). Newly allocated memory is unlikely to be found on L1D cache. OTOH, replacing data in recently accessed memory and reusing the memory is very likely to become L1D cache hit in runtime.

> is written in languages that inherited their array ordering from C

It’s not just C. Modern GPU hardware only supports row major memory layout for 2D and 3D textures (ignoring specialized layouts like swizzling and block compression but none of them are column major either). Modern image and video codecs only support row major layout for bitmaps.

What you wrote only applies to rotational latency, not seek latency. The seek latency is the time it takes for the head to reach the target. Heads only rotate within the small range like [ 0 .. 25° ], they are designed for rapid movements in either direction.

> would you know if there is something similar that works on u128 instead of just u32/u64?

Not as far as I’m aware, but I think your use case is handled by the u64 version rather well. Instead of u128, use array of two uint64 integers, pack the length into unused high bits of one of them.

Here’s example C++ https://godbolt.org/z/Mrfv3hrzr The packing function in that source file requires AVX2, unpack is scalar code based on that BMI1 instruction.

Another version with even fewer instructions to unpack, but one extra memory load: https://godbolt.org/z/hnaMY48zh Might be faster if you have a lot of these packed vectors, extracting numbers in a tight loop, and s_extractElements lookup table remains in L1D cache.

P.S. I’ve tested that code just a couple of times, might be bugs

The support for BMI1 instruction set extension is almost universal by now. The extension was introduced in AMD Jaguar and Intel Haswell, both launched in 2013 i.e. 12 years ago.

Instead of doing stuff like (word >> bit_offset) & self.mask, in C or C++ I usually write _bextr_u64, or when using modern C# Bmi1.X64.BitFieldExtract. Note however these intrinsics compile into 2 instructions not one, because the CPU instruction takes start/length arguments from lower/higher bytes of a single 16-bit number.

> full-platter seek time: ~8ms; half-platter seek time (avg): ~4ms

Average distance between two points (first is current location, second is target location) when both are uniformly distributed in [ 0 .. +1 ] interval is not 0.5, it’s 1/3. If the full platter seek time is 8ms, average seek time should be 2.666ms.

For FFTW the showstopper was GPL license. For IPP, 200 MB of binary dependencies, also I remember when Intel was caught testing for Intel CPUs specifically in their runtime libraries instead or CPUID feature bits, deliberately crippling performance on AMD CPUs. I literally don’t have any Intel CPUs left in this house. For cuFFT, the issue is vendor lock-in to nVidia.

And the problem is IMO too small to justify large dependencies. I only needed like 200×400 FFT as a minor component of a larger software.

I have recently needed a decently performing FFT. Instead of doing Cooley-Tukey, I have realized the bruteforce version essentially computes two vector×matrix products, so I have interleaved and reshaped the matrices for sequential full-vector loads, and did bruteforce version with AVX1 and FMA3 intrinsics. Good enough for my use case of moderately sized FFT where matrices fit in L2 cache.

Good article, but it uses less than ideal formula for weights of the gaussian blur kernel.

Gaussian function for coefficients is fine for large sigmas, but for small blur radius you better integrate properly. Luckily, C++ standard library has std::erf function you gonna need for the proper formula. Here’s more info: https://bartwronski.com/2021/10/31/practical-gaussian-filter...

C# would catch the bug at compile time, just like Rust.

https://www.rocksolidknowledge.com/articles/locking-asyncawa...

> does not account for frequency scaling on laptops

Are you sure about that?

> time spent in syscalls (if you don’t want to count it)

The time spent in syscalls was the main objective the OP was measuring.

> cycle counter

While technically interesting, most of the time I do my micro-benchmark I only care about wallclock time. Contradictory to what you see in search engines and ChatGPT, RDTSC instruction is not a cycle counter, it’s a high resolution wallclock timer. That instruction was counting CPU cycles like 20 years ago, doesn’t do that anymore.

Not sure if that’s relevant, but when I do micro-benchmarks like that measuring time intervals way smaller than 1 second, I use __rdtsc() compiler intrinsic instead of standard library functions.

On all modern processors, that instruction measures wallclock time with a counter which increments at the base frequency of the CPU unaffected by dynamic frequency scaling.

Apart from the great resolution, that time measuring method has an upside of being very cheap, couple orders of magnitude faster than an OS kernel call.

Good article, but I believe it lacks information what specifically these magical dFdx, dFdy, and fwidth = abs(dFdx) + abs(dFdy) functions are computing.

The following stackexchange answer addresses that question rather well: https://gamedev.stackexchange.com/a/130933/3355 As you see, dFdx and dFdx are not exactly derivatives, these are discrete screen-space approximations of these derivativities. Very cheap to compute due to the weird execution model of pixel shaders running in hardware GPUs.

Interestingly, a few months ago I wanted a similar thing for Windows. Ended up developing a simple tray utility for that. Probably the most important method is the handler of WM_POWERBROADCAST message: https://github.com/Const-me/SleepOnUnplug/blob/0.4/SleepOnUn...

For the last few years, I’ve been developing CAM/CAE software on my job, sometimes embedded Linux.

Same experience: last time I developed software written entirely in C++ was in 2008. Nowadays, only using C++ for DLLs consumed by C#, for 2 reasons: manually vectorized SIMD for CPU bound numerical stuff, and consuming C or C++ libraries like GPU APIs, MS Media Foundation, or Eigen.

I believe Java is more popular for enterprise and web apps.

.NET is widely used for videogames (games made with Unity, Godot, Unigine engines, also internal tools and game servers), desktop software, embedded software. Java is rarely used for these things, hence the results of that survey.

> Are there APIs which can sidestep the "load to CPU RAM" part?

On windows that API is Desktop Duplication. The API delivers D3D11 textures, usually in BGRA8_UNORM format. When HDR is enabled you would need slightly different API method which can deliver HDR frames in RGBA16_FLOAT pixel format.

For the sending side, a small buffer (which should implement a flush method called after serializing the complete message) indeed helps amortize costs of system calls. However, a buffer large enough for 1GB messages will waste too much memory. Without such buffer on the sender side, it’s impossible to prepend every message with the length: you don’t know the length of a serialized messages until the entire message is serialized.

With streamed serialization, the receiver doesn’t know when the message will end. This generally means you can’t optimize LEB128 decoding by testing high bits of 10 bytes at once.

For example, let’s say the message is a long sequence of strings. Serialized into a sequence of pairs [ length, payload ] length is var.int, payload is an array of UTF8 bytes of that length, and the message is terminated with a zero-length string.

You can’t implement data parallel LEB128 decoder for the length field in that message by testing multiple bytes at once because it may consume bytes past the end of the message. A decoder for MKV variable integers only needs 1-2 read calls to decode even large numbers, because just the first byte contains the encoded length of the var.int.

> you never serialize a byte by byte over the network

I sometimes do for the following two use cases.

1. When the protocol delivers real-time data, I serialize byte by byte over the network to minimize latency.

2. When the messages in question are large, like 1GB or more, I don’t want to waste that much memory on both ends of the socket to buffer complete messages like ProtoBuff does. On the sending side, I want to produce the message, encode at the same time with a streaming serializer, and stream bytes directly into the socket. Similarly, on the receiving side I want to de-serialize bytes as they come with a streaming de-serializer. Without buffering the complete message on sending side, receiving side can’t know length of the message in advance before receiving the complete message, because the sender only knows the length after the complete message is serialized.

> Actually there is - you can exploit the data parallelism

That doesn’t help much when you’re streaming the bytes, like many parsers or de-serializers do. You have to read bytes from the source stream one by one because each of the next byte might be the last one of the integer being decoded. You could workaround with a custom buffering adapter. Hard to do correctly, costs performance, and in some cases even impossible: when the encoded integers are coming in realtime from network, trying to read next few bytes into a RAM buffer may block.

With MKV variable integers, you typically know the encoded length from just the first byte. Or in very rare cases of huge uint64 numbers, you need 2 bytes for that. Once you know the encoded length, you can read the rest of the encoded bytes with a single read function.

Another thing, unless you are running on a modern AMD64 CPU which supports PDEP/PEXT instructions (parts of BMI2 ISA extension), it’s expensive to split/merge the input bits to/from these groups of 7 bits in every encoded byte. MKV variable integers don’t do that, they only need bit scan and byte swap, both instructions are available on all modern mainstream processors including ARM and are very cheap.

Great idea.

BTW, when I implementing similar logic in C#, I place expressions like ((xored - 0x01010101U) & ~xored & 0x80808080U) inside unchecked blocks. Because when I compile my C#, I set <CheckForOverflowUnderflow>true</CheckForOverflowUnderflow> compiler option.

On modern computers the performance impact of that option is negligible. I’ve encountered several cases where OverflowException produced by integer arithmetic exposed bugs which were trivial to fix, but would have been insanely hard to detect and debug without that compiler option.

> L1 cache is .. what.. 2 cycles?

On Zen 4 CPU, I believe the typical latency of L1D is 4 cycles. However, if you (or your compiler) write AVX code which adds these floats, will still bottleneck on memory even if both inputs are in L1D cache. Each Zen 4 core can sustain two vaddps instructions per cycle, two loads per cycle, and one store per cycle. Due to the load and store bottlenecks, that kernel will only do one vaddps per cycle i.e. will waste 50% of theoretically available compute power.

> Intel architects were privately telling us: "compute doesn't matter any more; it's all about memory speed"

To be fair, that’s only true for automatically vectorized code, kernels like in the GP’s example. With sufficient efforts spent on software development, for some practical problems it’s possible to write codes which do saturate compute.

An example of such problem is multiplication of large matrices. A carefully written manually vectorized implementation should bottleneck on compute not memory, because theoretically required memory bandwidth scales as N^2, while theoretically required FLOPs scale as N^3 where N is size of the matrix.

That’s precisely what many BLAS libraries are doing under the hood. For the same reason GPU vendors report ridiculously high numbers of theoretical TFlops when multiplying low precision matrices with these special AI blocks, wmma/mfma instructions on AMD, tensor cores on nVidia.

LEB128 is slow and there’s no way around that. I don’t know why so many data formats are using that codec.

The good variable integer encoding is the one used in MKV format: https://www.rfc-editor.org/rfc/rfc8794.html#name-variable-si... The compression win i.e. encoded size is equal to LEB128, however both encoding and decoding are way more efficient.

The encoder is a few fast instructions for all numbers no matter large or small: bit scan reverse (or leading zero count) to find count of bits required to store the input number, division by 7 rounding up to compute count of bytes (modern compiler reliably optimize into integer multiplication and bit shifts), bitwise shift + OR to set the VINT_MARKER bit, then byte swap to store in big endian format.

The decoder is equally efficient: compare first byte with 0 to detect numbers longer than 8 bytes (very rarely happens), bit scan reverse of either first or second byte to find encoded length, byte swap to load the big-endian format, then reset the most significant bit in the integer to get rid of the VINT_MARKER.

I believe the reason why management specifically asked for animated GIFs was compatibility. The GIF format is ancient and supported by everything, makes it trivial to share or embed these animation files.

Ignoring the compatibility, modern video codecs like h264 or h265 are substantially better than animated GIFs, in terms of both size and quality.

BTW I supported them as well. The only target platform of that software is modern versions of Windows. It only took couple pages of straightforward C++ because the OS includes a functional equivalent of libavcodec and libavformat libraries. Moreover, GPU drivers install and register the components to leverage the codecs implemented by hardware of these GPUs. The high-level API to encode compressed video files from a sequence of frames is MFCreateSinkWriterFromURL function.

I once did it for a closed-source CAM/CAE software. We wanted to generate high resolution and decent quality GIFs visualizing a progress of a numerical optimization in a few hundred animation frames. I wasn’t able to find a library which would deliver both reasonable size and good quality, so I made my own.

The trickiest part wasn’t the encoder; it’s computing the palette from RGB images. To minimize the output file size, I wanted a single palette shared by all frames.

The key piece of research was in that sample code from early 90-s https://www.ece.mcmaster.ca/~xwu/cq.c However, I had to rework it heavily because global variables and C language are too old school, also because FP32 precision is insufficient for the count of input pixels in my use case. 200 FullHD frames contain approximately 400M pixels, FP32 numbers don’t have the precision to accumulate that many of them. And the number is dangerously close to int32 limit, I have also upgraded the integer counters to int64.

I’m not sure it’s register allocation. VC++ is indeed less than ideal, but 2x performance difference is IMO too much to explain by register allocation alone.

First check that you’re passing correct flags to VC++ compiler and linker: optimized release configuration, correct /arch switch, and ideally LTCG. BTW if you’re using cmake build system it’s rather hard to do, cmake support of VC++ compiler is not great.

Another thing, VC++ doesn’t like emitting giant functions. A possible reason for 2x difference VC++ failed to inline stuff, and your function has calls to other functions instead of a single large one. Note the compiler supports __forceinline keyword to work around that.

Indeed, automatic vectorizers do such simple things pretty reliably these days.

However, if you build your software from kernels like that, you leave a lot of performance on the table. For example, each core of my Zen 4 CPU at base frequency can add FP32 numbers with AVX1 or AVX-512 at 268 GB/sec, which results in 806 GB/sec total bandwidth for your kernel with two inputs and 1 output.

However, dual-channel DDR5 memory in my computer can only deliver 83 GB/sec bandwidth shared across all CPU cores. That’s an order of magnitude difference for a single threaded program, and almost 2 orders of magnitude difference when computing something on the complete CPU.

Even worse, the difference between compute and memory widens over time. The next generation Zen 5 CPUs can add numbers twice as fast per cycle if using AVX-512.

For this reason, ideally you want your kernels to do much more work with the numbers loaded from memory. That’s why efficient compute kernels are often way more complicated than the for loop in your example. Sadly, seems modern compilers can only reliably autovectorize very simple loops.