Subscribe to RSS| purplesyringa.moe
Developers don’t usually divide numbers all the time, but hashmaps often need to compute remainders modulo a prime. Hashmaps are really common, so fast division is useful. For instance, rolling hashes might compute u128 % u64 with a fixed divisor. Compilers just drop the ball here: fn modulo(n: u128) -> u64 { (n % 0xffffffffffffffc5) as u64 } modulo: push rax mov rdx, -59 xor ecx, ecx call qword ptr [rip + __umodti3@GOTPCREL] pop rcx ret __umodti3 is a generic long division implementation, ...| purplesyringa's blog
The sentinel trick underlies a data structure with the following requirements: Read element by index in O ( 1 ) , Write element by index in O ( 1 ) , Replace all elements with a given value in O ( 1 ) . It is not a novel technique by any means, but it doesn’t seem on everyone’s lips, so some of you might find it interesting.| purplesyringa's blog
Rust’s approach to error handling comes at a cost. The Result type often doesn’t fit in CPU registers, and callers of fallible functions have to check whether the returned value is Ok or Err. That’s a stack spill, a comparison, a branch, and a lot of error handling code intertwined with the hot path that just shouldn’t be here, which inhibits inlining, the most important optimization of all. Exceptions and panics make it easy to forget about the occasional error, but they don’t suff...| purplesyringa's blog
$ base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 \ | base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 \ | base64 | head -1 Vm0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVU $ base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 \ | base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 | base64 \ | base64 | head -1 Vm0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3...| purplesyringa's blog
blazingio cuts corners by design. It keeps the constant factor small and uses long forgotten algorithms people used before processors supported SIMD and integer division. But another limitation made this task much harder. Size. Professional libraries start exceeding the Codeforces limit of 64 KiB really fast. Code minification barely helps, and neither does resorting to ugly code. So I cut a corner I don’t typically cut. Undefined Behavior. These two words make a seasoned programmer shudder...| purplesyringa's blog
I have recently done some performance work and realized that reading about my experience could be entertaining. Teaching to think is just as important as teaching to code, but this is seldom done; I think something I’ve done last month is a great opportunity to draw the curtain a bit. serde is the Rust framework for serialization and deserialization. Everyone uses it, and it’s the default among the ecosystem. serde_json is the official serde “mixin” for JSON, so when people need to pa...| purplesyringa's blog