The Curious Engineer

All blogs / Performance / optimization

Paul Khuong: some Lisp

pvk.ca

Paul Khuong's personal blog. Some Lisp, some optimisation, mathematical or computer.

Performance / optimizationAlgorithms / data structuresLisp / Clojure / SchemeConcurrencyMath

’15’20’25
Posts
65 from 18 Jan 2012 to 30 Dec 2025
Posting
now and then (2 in the last year)
Kind
personal blog
Feed
https://pvk.ca/atom.xml

2025 2

  1. Six versions accessing: wait-free protected versions with bounded cardinality
  2. Monoid-augmented FIFOs, deamortised

2024 1

  1. VPTERNLOG: when three is 100% more than two

2022 3

  1. Fixing the hashing in "Hashing modulo α-equivalence"
  2. Plan B for UUIDs: double AES-128
  3. Hacking tips for Linux perf porcelain

2021 5

  1. Bounded dynamicism with cross-modifying code
  2. Slitter: a slab allocator that trusts, but verifies
  3. Entomological solutions
  4. Baseline implementations should be predictable
  5. Stuff your logs!

2020 7

  1. 1.5x the PH bits for one more CLMUL
  2. UMASH: a fast and universal enough hash
  3. Flatter wait-free hazard pointers
  4. Check for borrows in bitwise operations
  5. How hard is it to guide test case generators with branch coverage feedback?
  6. Too much locality... for stores to forward
  7. Lazy Linear Knapsack

2019 5

  1. A multiset of observations with constant-time sample mean and variance
  2. A couple of (probabilistic) worst-case bounds for Robin Hood linear probing
  3. Fractional set covering with experts
  4. The unscalable, deadlock-prone, thread pool
  5. membarrier(2)

2018 3

  1. Restartable sequences with the polysemic null segment selector
  2. The Confidence Sequence Method: a computer-age test for statistical SLOs
  3. An old conjecture on stream transducers

2017 5

  1. How to print integers really fast (with Open Source AppNexus code!)
  2. Rendezvous hashing: my baseline "consistent" distribution method
  3. Chubanov's projection methods for 0/1 programming
  4. Relaxed revocable locks: mutual exclusion modulo preemption
  5. Three-universal hashing in four instructions

2015 4

  1. Retrospective on binary search and comp{ress,ilat}ion
  2. Linear-log bucketing: fast, versatile, simple
  3. Pointer-less Scapegoat Trees
  4. Lock-free sequence locks

2014 12

  1. Performance tuning ~ writing an essay
  2. Doodle: hybridising SBCL's GENCGC with mark and sweep
  3. How to define new intrinsics in SBCL
  4. Integer division, step 0: no remainder
  5. K-ary heapsort: more comparisons, less memory traffic
  6. Number systems for implicit data structures
  7. Refactoring with LZ77: compression is compilation (?)
  8. What I look for in GSoC proposals
  9. SBCL: the ultimate assembly code breadboard
  10. Reference books I'm bringing across the border
  11. How bad can 1GB pages be?
  12. A whirlwind introduction to decomposition methods in discrete optimisation

2013 7

  1. So you want to write an LP solver (a.k.a. My Little LP: Cholesky Is Magic)
  2. The other Robin Hood hashing
  3. The weaknesses of SBCL's type propagation
  4. All you need is call/cc
  5. Bitsets match regular expressions, compactly
  6. Fresh in SBCL 1.1.8: SSE intrinsics!
  7. Starting to hack on SBCL

2012 11

  1. The eight useful polynomial approximations of `sinf(3)'
  2. Tabasco Sort: a super-optimal merge sort
  3. On the importance of keeping microbenchmarks honest
  4. A one-instruction write barrier
  5. Engineering a list merge sort
  6. Binary search is a pathological case for caches
  7. Binary search *eliminates* branch mispredictions
  8. Fitting polynomials by generating linear constraints
  9. Finally! Napa-FFT3 is ready for users
  10. Fixed Points and Strike Mandates
  11. Migration and Synopsis