Andrey Minogin

JVM & PostgreSQL performance

Tag: Performance

  • The flame graph was wrong by 57×. So I’m building a profiler.

    The flame graph was wrong by 57×. So I’m building a profiler.

    This is the first post about it — why we would ever need a new profiler, and where the existing tools fall short. 

    Short version: on Apache Calcite’s planner, a flame graph put a rule at 0.81% when it was actually eating 46% of the time — and ranked it sixth. 

    The code that has no hot spot

    Some systems have a hot method. You profile them, one frame is red, you fix it, you go home.

    Then there are systems where the same twenty operations run billions of times, each one taking tens of nanoseconds — a map lookup, a filter check, one edge of a graph traversal. Nothing is hot. Everything is warm. The flame graph is a smooth carpet of HashMap.putVal and ArrayList.indexOfRange, and every one of those attributions is correct and none of them is anything you can act on. Nobody is going to fix HashMap.

    The question you actually have is not “which method is hot”. It is “which of my domain operations is eating the time” — expanding a frontier, matching a rule, evaluating a predicate.

    A stack profiler cannot answer that, and the reason is more interesting than it first looks.

    The receiver is missing from the stack

    A stack frame records which code ran: declaring class, method, line. It does not record what the code ran on. The receiver is sitting right there in this, but no stack walker dereferences it — walking a stack has to stay cheap and, in a signal handler, safe.

    Usually that doesn’t matter, because the method name is a good enough proxy for what happened. It stops being good enough the moment your operations are objects dispatched through shared code — rules in a planner, handlers in a router, operators in an interpreter, message types in a broker. Then the identity you care about is exactly the part that isn’t recorded.

    Here is the sharpest example I have, and it’s from real code I didn’t write: Apache Calcite’s query planner.

    Kotlin
    // simplified — Calcite's ConverterRule
// almost no rule overrides onMatch
public void onMatch(RelOptRuleCall call) {
    // each rule implements only this: build one node and return
    RelNode converted = convert(rel);

    // the base class does the rest: register the node,
    // which re-fires every rule against it
    call.transformTo(converted);
}

    About twenty distinct optimization rules inherit that one onMatch and don’t override it. They are twenty different objects going through one method body. In my profile, ConverterRule.onMatch holds 49% of planning time — and there is nothing in the recording that can split it, because the difference between those twenty rules lives entirely in a field the profiler never reads.

    And that makes the flame graph 57 times wrong

    “Fine,” you say, “but convert is implemented per rule, so the name is one frame deeper. Just read it.”

    It is there. And it is a trap. convert builds one node and returns; the expensive part — transformTo and the re-registration cascade under it — runs after it returns, under the base class’s frame. The subclass frame encloses the cheap half of its own firing.

    Measured: EnumerableMergeJoinRule appears in 0.81% of samples. Its actual share of planning time is 46%. The flame graph is wrong by a factor of 57, and it ranks that rule sixth while putting a 30% rule first. Not “failed to answer” — answered confidently, in the wrong order, and the reader goes and optimises the wrong thing.

    The nastiest part: in the same recording, rules that do override onMatch are attributed perfectly — 30.16% from the stacks against 30.21% from my instrument. So one profile is exact for one rule and off by 57× for another, and nothing in it tells you which case you’re in. The difference lives inside a base class you’ve never read.

    (How I know the 46% is the real number is the subject of a later article in this series.)

    46% of the time, 275× when removed

    When the profiler doesn’t answer, everyone falls back to the same move: switch the thing off, run it again, compare. It is the only technique that answers the question you actually have — what happens if I don’t do this.

    On Calcite, removing that heavy 46% EnumerableMergeJoinRule took planning from 17.8 s to 64.7 ms. 275×.

    Which is a spectacular result and not the cost of the rule. That rule shapes the search space, so the run without it explored a much smaller one — the fast run wasn’t the same problem minus one part, it was an easier problem. I had seen this before: on a graph traversal I worked on for a year, switching a piece of logic off made the traversed graph itself smaller, and every measurement I took that way was contaminated the same way.

    (This doesn’t mean Calcite should drop merge join — my workload just had nothing sorted for it to exploit.)

    So there are two different numbers here: where the time went, and what you’d actually get back by not spending it. A profiler only ever prints the first one. Here they were two orders of magnitude apart — because the rule wasn’t just spending its own 46%, it was making work for every other rule too.

    What I’m building

    A profiler that attributes time to your operations — the ones you named — instead of to the methods they happen to run through.

    The mechanism is one integer: each thread holds the id of the operation it is currently inside, and a separate thread reads every slot once a millisecond and counts.

    Kotlin
    val mergeJoin = register("mergeJoin")   // once, at startup

op(mergeJoin) { rule.onMatch(call) }    // at the call site

    The id comes from the object, not the stack — so twenty rules sharing one method body produce twenty different numbers. And because the share of samples landing on an id is that operation’s share of time, an operation four orders of magnitude shorter than the sampling interval is no problem at all: precision comes from the number of samples, not the resolution of a clock. You don’t measure a nanosecond operation, you count how often you catch threads inside it.

    The boundary costs about 1.7 ns, which is why you can wrap a 200 ns operation in one. System.nanoTime() costs ten times that.

    None of this is new. Go has had it in the runtime for years as pprof labels. The JVM has no equivalent you can simply pick up — what exists is either part of a commercial APM or a low-level API with the rest left to you.

    What’s next in the series

    • The bench. A profiler cannot validate itself. Building something to check it against caught three of my own mistakes, including a comparison that said the instrumented run was 15% faster than the uninstrumented one.
    • The Calcite trial in full — including 12 points of discrepancy I still can’t account for.

    Further out: the same sampler takes every thread in one pass, which makes one tick a snapshot of how many threads were actually working. A flame graph cannot answer that — it sums across threads by construction. That’s the part I’m most curious about.

  • Immutability vs concurrency: making a fast graph writable

    Immutability vs concurrency: making a fast graph writable

    In my last article I promised to explain how the in-memory graph could be modified in real-time without losing high traversal throughput.

    The structure in question is this:

    Kotlin
    val graph = IntObjectHashMap<IntArrayList>()

    Every map entry is a bunch of edges, where key is the source node id and value is the list of target node ids.

    A common requirement is to regularly sync this in-memory structure with the database. We assume that writes are small and not frequent compared to reads.

    Immutability vs concurrency

    To make this structure updatable we could use two general mechanisms — immutability and concurrency. Immutability means we create a new object instead of editing the existing one, and replace the reference. Concurrency means we use locks to ensure the data is not modified and accessed at the same time.

    First we must agree that the whole map cannot be made immutable as it consumes a lot of memory and takes a long time to populate. HPPC collections are non thread-safe so we need to wrap the map into some concurrent structure.

    Optimistic locking

    A naive approach would be to synchronize access to the map, but it will kill the whole idea of a high-performance map, as reads don’t need to be synchronized with each other while writes are rare. Alternatively we might use a non-exclusive lock for reads and exclusive lock for writes, but that still means acquiring a lock on every read operation which is expensive.

    There’s a better alternative — optimistic locking (based on a version counter rather than a lock). We try to read from the map without acquiring a lock, and then we check if there was no write intervention. If someone wrote to the map in the meantime, we could either repeat the read or switch to a read lock.

    To make this convenient let’s draft a utility for optimistic locking.

    Caution: code in this article has flaws and is only used as a simplified example!

    Kotlin
    class OptimisticLock {
    // This one has all the capabilities we need
    private val lock = StampedLock()
    
    fun <T> blockingWrite(block: () -> T): T {
        // An exclusive write lock
        val stamp = lock.writeLock()
        try {
            return block()
        } finally {
            lock.unlockWrite(stamp)
        }
    }

    fun <T> blockingRead(block: () -> T): T {
        // A non-exclusive read lock
        val stamp = lock.readLock()
        try {
            return block()
        } finally {
            lock.unlockRead(stamp)
        }
    }

    fun <T> optimisticRead(block: () -> T): T {
        val stamp = lock.tryOptimisticRead()

        // stamp == 0 means there's a write in-progress
        if (stamp != 0L) {
            val result = try {
                block()
            } catch (e: RuntimeException) {
                if (!lock.validate(stamp)) return blockingRead(block)
                throw e
            }
            // validate returns true if there was no intervening write
            if (lock.validate(stamp)) return result
        }
        return blockingRead(block)
    }
}

    Notice the try / catch inside the optimistic read function. It’s not just a dummy protection, the block() execution is dangerous as it runs in a concurrent environment without any thread safety. In our case keys and mask fields of IntObjectHashMap can get out of sync which will cause an ArrayIndexOutOfBoundsException. But if we know that it happened due to concurrent access we can safely switch to blocking read instead of rethrowing the exception.

    A few things to improve here if you are going to use this code:

    1. Inline the block calls.
    2. Try optimistic read 2-3 times before switching to blocking read.
    3. Make sure to not allow writes within read blocks.
    4. Fix possible infinite loop inside block() call due to concurrent write.
    5. Beware of StampedLock non-reentrancy.

    Immutable nested lists

    Using the above technique we could make the whole map concurrent without hurting read performance. So what about the nested lists? We could also make them concurrent but this means introducing a huge amount of locks (one per source node) while it’s highly improbable that we will write the same list concurrently.

    In this case it’s much easier to make nested lists immutable and replace them as a whole. But, again, HPPC does not provide an immutable version of IntArrayList, so let’s create one.

    Kotlin
    class ImmutableIntArrayList(values: IntArray) {
    private val list = IntArrayList(values.size).apply {
        add(values, 0, values.size)
    }

    fun get(index: Int) = list[index]

    val size = list.size()
}

    Final high-throughput solution

    Now let’s put it all together.

    Kotlin
    class ConcurrentGraph {
    private val graph = IntObjectHashMap<ImmutableIntArrayList>()
    private val lock = OptimisticLock()

    fun get(fromId: Int): ImmutableIntArrayList? =
        lock.optimisticRead { graph.get(fromId) }

    fun put(fromId: Int, toIds: ImmutableIntArrayList) {
        lock.blockingWrite { graph.put(fromId, toIds) }
    }
}

    One more thing to consider. If you perform a large-scale read operation, for example counting the edges, you should use blocking read as the optimistic read most probably will not succeed and the whole operation will need to be restarted.

    Kotlin
    fun countEdges(): Int =
    lock.blockingRead { graph.sumOf { it.value.size } }

    Also if you are going to perform multiple writes in a batch consider something like this to acquire lock just once.

    Kotlin
    inner class WriteScope internal constructor() {
    fun put(fromId: Int, toIds: ImmutableIntArrayList) {
        graph.put(fromId, toIds)
    }
}

fun write(block: WriteScope.() -> Unit) {
    lock.blockingWrite { WriteScope().block() }
}

    Usage:

    Kotlin
    graph.write {
    put(1, ids1)
    put(2, ids2)
    put(3, ids3)
}
  • When Postgres is the wrong place to traverse the graph

    When Postgres is the wrong place to traverse the graph

    Some performance problems are not query-optimization problems. You can index, rewrite, tune parameters, throw hardware at it — and still lose, because the work simply doesn’t belong in the database. The fix isn’t a better query. It’s moving the work somewhere else.

    The task

    Imagine you perform a deep search in a huge graph — think of finding level-N friends in a social network or tier-N product parts in a bill of materials. You start from some node, visit all its nearest neighbours and recursively continue from there (breadth-first search) or recursively traverse every path (depth-first search).

    With Postgres the standard approach is to store (node A, node B) edge tuples in the database and apply recursive CTEs to query the graph.

    SQL
    WITH RECURSIVE r(node, depth, path) AS (
  SELECT       -- Start with the first node
    :first_node AS node,
    0 AS depth,
    ARRAY[:first_node] AS path
  UNION ALL
  SELECT       -- Recursively find next node
    g.b AS node,
    r.depth + 1 AS depth,
    r.path || g.b AS path
  FROM graph g
  JOIN r ON r.node = g.a
  WHERE g.b <> ALL(r.path)    -- Guard against cycles
)
SELECT *
FROM r;

    The problem

    There are two main parameters affecting the performance of graph traversal: the branching factor b — average number of node connections, and the depth of traversal D.

    Whatever you do you eventually hit the O(b^D) wall. The average number of nodes to traverse grows exponentially with D. There’s no algorithmic way you can do deep search asymptotically faster (no, quantum computing would not help either).

    As your database grows the b will most probably increase, and as your business grows there will certainly be a demand to increase D. This means you would be constantly stuck with search time regressing from milliseconds to minutes. You could fight this by first using materialized CTEs, then switching to temporary tables with indexes, but all those efforts would be immediately swallowed by a slight increase of search depth.

    Another important issue is that Postgres cannot perform depth-first search, the SEARCH DEPTH FIRST does not change the algorithm under the hood. This means that at depth N you need to store ~b^N frontier nodes.

    The solution

    First of all you need to switch to the depth-first search to only store the current path in the memory, not the whole frontier. Then, as you cannot work around the general O(b^D) limitations of the algorithm, you should optimize each basic operation for speed and memory consumption to its limits.

    We should load the whole graph into the memory and make it effectively accessible. The main operation is finding the neighbours of the current node. For the most optimal access we need a map whose key is the node id and whose value is the list of connected nodes.

    Standard approach assuming node id is Int would be

    Kotlin
    val graph: Map<Int, List<Int>> = hashMapOf()

    But here comes the huge inefficiency. Maps and lists in Java operate on boxed values. Every id becomes a boxed Integer: a separate heap object — a 12-byte header plus the 4-byte value, ~16 bytes total — plus a 4–8 byte reference to reach it. Compare that to 4 bytes for a raw int. Accessing such a map is also slower: each lookup chases a pointer to a scattered heap object — a likely cache miss — and then unboxes it. 

    This could be overcome by using specialized Java collection libraries such as HPPC (High Performance Primitive Collections) which operate over unboxed values instead. See Reducing memory usage 10 times with High-Performance Primitive Collections

    In our example the graph would become:

    Kotlin
    val graph: IntObjectMap<IntList> = IntObjectHashMap()

    And as shown in the referenced article this leads to up to 10x less memory consumption. The latency improvement is usually even more substantial.

    One additional optimization is to prematurely filter the nodes, throwing away whole subgraphs if the node or edge does not satisfy certain conditions.

    You should also decide whether you actually need all paths to each node, or just the reachable nodes. If only distinct target nodes matter, a visited-set collapses the exponential blow-up toward linear! This is also something much easier to implement outside of SQL.

    A note on concurrency

    If you are going to update the graph in real time you need to make it writable. Here comes the trade-off — making the whole graph immutable and replacing it every time is too expensive, especially if the changes are minor. But making every element concurrently writable is also expensive.

    A possible solution might be to combine the two approaches:

    Kotlin
    val graph: ConcurrentIntObjectMap<IntList> = ConcurrentIntObjectHashMap()

    Keep the relatively small IntList values immutable and swap them wholesale, while making the outer map concurrently accessible via optimistic locking. This is not natively supported by HPPC, I will show the exact implementation in one of the next articles.

    The lesson

    The useful skill here isn’t using primitive collections or optimistic locking. The value comes from seeing the architectural flaw and moving application parts to where they actually belong.

    When you optimize SQL queries you see the solution as a better query plan, not as a conceptual shift. Sometimes it helps to stop fighting, zoom out and start from scratch.

  • Reducing memory usage 10 times with High-Performance Primitive Collections

    Kotlin basic types such as Int or Double correspond to high-performance Java primitive types such as int or double. But nullable (Int?) and generic (<Int>) versions of those types are mapped to boxed Java types such as Integer or Double.

    Boxed types are memory heavy. Let’s make a simple comparison.

    Kotlin
    @Test
fun `memory occupied by primitive int`() {
    data class A(
        val x: Int
    )

    val N = 100_000_000

    val mem1 = calculateOccupiedMemoryMB()

    val list = List(N) { A(it) }

    val mem2 = calculateOccupiedMemoryMB()

    println("Occupied memory: ${mem2 - mem1} MB")

    list
}

> Occupied memory: 1910 MB
    Kotlin
    @Test
fun `memory occupied by boxed Int`() {
    data class A(
        val x: Int?
    )

    val N = 100_000_000

    val mem1 = calculateOccupiedMemoryMB()

    val list = List(N) { A(it) }

    val mem2 = calculateOccupiedMemoryMB()

    println("Occupied memory: ${mem2 - mem1} MB")

    list
}

> Occupied memory: 3436 MB

    We already see almost 2x difference, but actually it’s more serious as our test is not accurate enough.

    Code explained

    calculateOccupiedMemoryMB measures the diff between total and occupied memory running garbage collection for at least 3 seconds in advance to reduce the garbage footprint.

    Kotlin
    fun calculateOccupiedMemoryMB(): Int {
    getRuntime().gc()
    Thread.sleep(3000)
    return ((getRuntime().totalMemory() - getRuntime().freeMemory()) / (1024 * 1024)).toInt()
}

    list reference at the end of the block is a trick to avoid JVM optimization. If JVM sees an object is not used it might wipe it off the RAM.

    What if we need a huge Set of Int‘s or a huge Map of Int to Object? Unfortunately standard Java Collections are based on generics which means all of the objects will be autoboxed.

    Here HPPC: High Performance Primitive Collections comes to the rescue. This library has predefined collection for all the primitive types.

    Let’s compare memory footprints of a normal Java HashSet<Int> and a corresponding HPPC IntHashSet.

    Kotlin
    @Test
fun `memory occupied by HashSet`() {
    val N = 100_000_000

    val mem1 = calculateOccupiedMemoryMB()

    val set = hashSetOf<Int>()
    repeat(N) { set.add(it) }

    val mem2 = calculateOccupiedMemoryMB()

    println("Occupied memory: ${mem2 - mem1} MB")

    1 in set
}

> Occupied memory: 5098 MB
    Kotlin
    @Test
fun `memory occupied by HashSet`() {
    val N = 100_000_000

    val mem1 = calculateOccupiedMemoryMB()

    val set = IntHashSet()
    repeat(N) { set.add(it) }

    val mem2 = calculateOccupiedMemoryMB()

    println("Occupied memory: ${mem2 - mem1} MB")

    1 in set
}

> Occupied memory: 518 MB

    10 times less memory used!