# Database Architects A blog by and for database architects. This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles. ## Safe Optimistic Lock Coupling DevFeed: [Safe Optimistic Lock Coupling]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2026-04-29T10:22:56Z Content type: article Language: en Sources: [Database Architects]() Topics: [Concurrency](), [Concurrent Programming](), [Data structures](), [Scalability](), [race-condition]() Tags: [concurrent](), [cpu](), [data-structures](), [locking](), [locks](), [mutex](), [performance](), [race-condition](), [scalability](), [synchronization](), [thread](), [typesafety]() ### AI overview The article explains how lock coupling can limit the scalability of concurrent binary-tree lookups because readers contend on locks, especially at the root. It presents Optimistic Lock Coupling, in which readers validate version numbers without writes, and discusses the race-condition risk when values are used before validation. ### Source excerpt As the number of CPU cores keeps growing, the scalability of concurrent data structures becomes increasingly important. A data structure that works fine on 4 cores can become a bottleneck on 32, not because of algorithmic limitations, but because of how it synchronizes access. We illustrate that with a simple binary tree. Usually these data structures are protected by some kind of lock: struct Node { mutex lock; key_type key; value_type value; Node* left, *right; }; struct Tree { mutex lock; Node* root; }; When searching a value, we can traverse the data structure, lock the parts of the data we are currently touching, and release locks when we are done ("lock coupling"): option Tree::lookup(key_type key) { lock.lock_shared(); mutex* currentLock = &lock; Node* iter = root; option result; while (iter) { if (key == iter->key) { result = iter->value; break; } Node* next = (key < iter->key) ? iter->left : iter->right; if (next) next->lock.lock_shared(); currentLock->unlock(); currentLock = next ? &next->lock : nullptr; iter = next; } currentLock->unlock(); return result; } While conceptually simple, lock coupling has quite poor performance in practice. The problem is that it creates contention on the locks, in particular for the root node. Every lookup goes through the root node, thus the root node is constantly locked and unlocked. While there is no semantic contention between lookups, as all readers can read the root concurrently, there is physical contention on the lock itself, which limits scalability. This can be seen below, with concurrent lookups in a tree of 100,000 elements, executed on a 16-core / 32-thread 9950X3D. Lookup scalability: no locking vs lock coupling This contention problem can be solved by using Optimistic Lock Coupling, a synchronization technique where readers do not perform any writes. The key idea here is that writers lock as usual, and increase a version number when they are done updating. Readers read the version numb ## Comparing Integers and Doubles DevFeed: [Comparing Integers and Doubles]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2025-11-10T16:55:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [floating-point](), [SQL](), [DuckDB](), [sql-server](), [Programming](), [C++]() Tags: [c-plus-plus](), [compiler](), [duckdb](), [floating-point](), [precision](), [sql](), [sql-server](), [testing](), [undefined-behavior]() ### AI overview The article explains how comparing large integers with double-precision values can lose integer precision and produce non-transitive results in SQL systems. It describes how this can cause differences between ordinary comparisons and hash joins, and outlines a conversion-based approach for correct comparisons. ### Source excerpt During automated testing we stumbled upon a problem that boiled down to transitive comparisons: If a=b, and a=c, when we assumed that b=c. Unfortunately that is not always the case, at least not in all systems. Consider the following SQL query: select a=b, a=c, b=c from (values( 1234567890123456789.0::double precision, 1234567890123456788::bigint, 1234567890123456789::bigint)) s(a,b,c) If you execute that in Postgres (or DuckDB, or SQL Server, or ...) the answer is (true, true, false). That is, the comparison is not transitive! Why does that happen? When these systems compare a bigint and a double, they promote the bigint to double and then compare. But a double has only 52 bits of mantissa, which means it will lose precision when promoting large integers to double, producing false positives in the comparison. This behavior is highly undesirable, first because it confuses the optimizer, and second because (at least in our system) joins work very differently: Hash joins promote to the most restrictive type and discard all values that cannot be represented, as they will never produce a join partner for sure. For double/bigint joins that leads to observable differences between joins and plain comparisons, which is very bad. How should we compare correctly? Conceptually the situation is clear, an IEEE 754 floating point with sign s, mantissa m, and exponent e represents the values (-1)^s*m*2^e, we just have to compare the integer with that value. But there is no easy way to do that, if we do a int/double comparison in, e.g., C++, the compiler does the same promotion to double, messing up the comparison. We can get the logic right by doing two conversions: We first convert the int to double and compare that. If the values are not equal, the order is clear and we can use that. Otherwise, we convert the double back to an integer and check if the conversion rounded up or down, and handle the result. Plus some extra checks to avoid undefined behavior (the conversion of intma ## Advent of Code 2024 in pure SQL DevFeed: [Advent of Code 2024 in pure SQL]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2024-12-27T16:57:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [SQL](), [Advent of Code](), [Algorithms](), [Programming](), [Graphs]() Tags: [advent-of-code](), [algorithm](), [duckdb](), [parsing](), [postgres](), [puzzle](), [recursive-sql](), [sql]() ### AI overview The author describes solving every Advent of Code 2024 problem in pure SQL. Small-scale traversals were practical and sometimes pleasant, while larger recursive queries could be inefficient and require more than 200 GB of memory. The experience suggests that recursive SQL would benefit from mechanisms for updating state and supporting more complex control flow. ### Source excerpt On a whim I decided to do this years advent of code in pure SQL. That was an interesting experience that I can recommend to everybody because it forces you to think differently about the problems. And I can report that it was possible to solve every problem in pure SQL. In many cases SQL was actually surprisingly pleasant to use. The full solution for day 11 (including the puzzle input) is shown below: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30with recursive aoc10_input(i) as (select ' 89010123 78121874 87430965 96549874 45678903 32019012 01329801 10456732 '), lines(y,line) as ( select 0, substr(i,1,position(E'\n' in i)-1), substr(i,position(E'\n' in i)+1) from aoc10_input union all select y+1,substr(r,1,position(E'\n' in r)-1), substr(r,position(E'\n' in r)+1) from lines l(y,l,r) where position(E'\n' in r)>0 ), field(x,y,v) as ( select x,y,ascii(substr(line,x::integer,1))-48 from (select * from lines l where line<>'') s, lateral generate_series(1,length(line)) g(x) ), paths(x,y,v,sx,sy) as ( select x,y,9,x,y from field where v = 9 union all select f.x,f.y,f.v,p.sx,p.sy from field f, paths p where f.v=p.v-1 and ((f.x=p.x and abs(f.y-p.y)=1) or (f.y=p.y and abs(f.x-p.x)=1)) and p.v>0), results as (select * from paths where v=0), part1 as (select distinct * from results) select (select count(*) from part1) as part1, (select count(*) from results) as part2 Parsing the input is a bit painful in SQL, but it is not too bad. Lines 1-10 are simply the puzzle input, lines 11-17 split the input into individual lines, and lines 18-21 construct a 2D array from the input. The algorithm itself is pretty short, lines 22-27 perform a recursive traversal of the field, and lines 28-39 extract the puzzle answer from the traversal results. For this kind of small scale traversals SQL works just fine. Other days were more painful. Day 16 for example does conceptually a very similar traversal of a field, and it computes the minimal traversal distance ## Important Data Systems Problems Understudied by Database Research DevFeed: [Important Data Systems Problems Understudied by Database Research]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2024-12-13T07:37:00Z Content type: opinion Language: en Sources: [Database Architects]() Topics: [data](), [systems](), [Database](), [Compression](), [Amazon Redshift]() Tags: [amazon-redshift](), [analysis](), [compression](), [data](), [distributed](), [paper](), [performance](), [research](), [standard](), [storage](), [systems]() ### AI overview This discussion of database research priorities highlights variable-length string processing, database-specific string compression, unrealistic benchmarks, and the need for more representative analytical workloads. It also notes challenges in distributed query processing. ### Source excerpt In November, I had the pleasure of attending the Dutch-Belgian DataBase Day, where I moderated a panel on practical challenges often overlooked in database research. Our distinguished panelists included Allison Lee (founding engineer at Snowflake), Andy Pavlo (professor at CMU), and Hannes Mühleisen (co-creator of DuckDB and researcher at CWI), with attendees contributing to the discussion and sharing their perspectives. In this post, I'll attempt to summarize the discussion in the hope that it inspires young (and young-at-heart) researchers to tackle these challenges. Additionally, I'll link to some paper that can serve as motivation and starting points for research in these areas. One significant yet understudied problem raised by multiple panellists is the handling of variable-length strings. Any analysis of real-world analytical queries reveals that strings are ubiquitous. For instance, Amazon Redshift recently reported that around 50% of all columns are strings. Since strings are typically larger than numeric data, this implies that strings are a substantial majority of real-world data. Dealing with strings presents two major challenges. First, query processing is often slow due to the variable size of strings and the (time and space) overhead of dynamic allocation. Second, surprisingly little research has been dedicated to efficient database-specific string compression. Given the importance of strings on real-world query performance and storage consumption, it is surprising how little research there is on the topic (there are some exceptions). Allison highlighted a related issue: standard benchmarks, like TPC-H, are overly simplistic, which may partly explain why string processing is understudied. TPC-H queries involve little complex string processing and don't use strings as join or aggregation keys. Moreover, TPC-H strings have static upper bounds, allowing them to be treated as fixed-size objects. This sidesteps the real challenges of variable-size strings ## C++ exception performance three years later DevFeed: [C++ exception performance three years later]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2024-12-10T14:44:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [C++](), [Exception](), [Scalability](), [gcc](), [JIT](), [LLVM]() Tags: [benchmark](), [c-plus-plus](), [clang](), [exception](), [gcc](), [glibc](), [jit](), [llvm](), [performance](), [series]() ### AI overview The article reviews improvements to C++ exception unwinding performance. Lock-free lookup mechanisms in glibc and libgcc improve scalability for statically generated and JIT-generated code, although clang's implementation may still have scaling limitations. ### Source excerpt About three years ago we noticed serious performance problems in C++ exception unwinding. Due to contention on the unwinding path these became more and more severe the more cores a system had, and unwinding could slow down by orders of magnitude. Due to the constraints of backwards compatibility this contention was not easy to eliminate, and P2544 discussed ways to fix this problem via language changes in C++. But fortunately people found less invasive solutions. First, Florian Weimer changed the glibc to provide a lock-free mechanism to find the (static) unwind tables for a given shared object. Which eliminates the most serious contention for "simple" C++ programs. For example in a micro-benchmark that calls a function with some computations (100 calls to sqrt per function invocation), and which throws with a certain probability, we previously had very poor scalability with increasing core count. With his patch we now see with gcc 14.2 on a dual-socket EPYC 7713 the following performance development (runtime in ms): 1 2 4 8 16 32 64 128 threads 0% failure 29 29 29 29 29 29 29 42 0.1% failure 29 29 29 29 29 29 29 32 1% failure 29 30 30 30 30 30 32 34 10% failure 36 36 37 37 37 37 47 65 Which is more or less perfect. 128 threads are a bit slower, but that is to be expected as one EPYC only has 64 cores. With higher failure rates unwinding itself becomes slower but that is still acceptable here. Thus most C++ programs are just fine. For our use case that is not enough, though. We dynamically generate machine code at runtime, and we want to be able to pass exceptions through generated code. The _dl_find_object mechanism of glibc is not used for JITed code, instead libgcc maintains its own lookup structure. Historically this was a simple list with a global lock, which of course had terrible performance. But through a series of patches we managed to change libgcc into using a lock-free b-tree for maintaining the dynamic unwinding frames. Using a similar experiment to the ## B-trees Require Fewer Comparisons Than Balanced Binary Search Trees DevFeed: [B-trees Require Fewer Comparisons Than Balanced Binary Search Trees]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2024-06-06T13:59:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Data structures](), [data]() Tags: [comparisons](), [data-structure](), [structure](), [theory]() ### AI overview The article compares B-trees with balanced binary search trees by analyzing the number of comparisons required for lookup operations. It explains that as the B-tree degree increases, the comparison bound approaches the lower bound, and for degree k>=8, B-trees are guaranteed to use fewer comparisons than AVL trees. ### Source excerpt Due to better access locality, B-trees are faster than binary search trees in practice -- but are they also better in theory? To answer this question, let's look at the number of comparisons required for a search operation. Assuming we store n elements in a binary search tree, the lower bound for the number of comparisons is log2 n in the worst case. However, this is only achievable for a perfectly balanced tree. Maintaining such a tree's perfect balance during insert/delete operations requires O(n) time in the worst case. Balanced binary search trees, therefore, leave some slack in terms of how balanced they are and have slightly worse bounds. For example, it is well known that an AVL tree guarantees at most 1.44 log2 n comparisons, and a Red-Black tree guarantees 2 log2 n comparisons. In other words, AVL trees require at most 1.44 times the minimum number of comparisons, and Red-Black trees require up to twice the minimum. How many comparisons does a B-tree need? In B-trees with degree k, each node (except the root) has between k and 2k children. For k=2, a B-tree is essentially the same data structure as a Red-Black tree and therefore provides the same guarantee of 2 log2 n comparisons. So how about larger, more realistic values of k? To analyze the general case, we start with a B-tree that has the highest possible height for n elements. The height is maximal when each node has only k children (for simplicity, this analysis ignores the special case of underfull root nodes). This implies that the worst-case height of a B-tree is logk n. During a lookup, one has to perform a binary search that takes log2 k comparisons in each of the logk n nodes. So in total, we have log2 k * logk n = log2 n comparisons. This actually matches the best case, and to construct the worst case, we have to modify the tree somewhat. On one (and only one) arbitrary path from the root to a single leaf node, we increase the number of children from k to 2k. In this situation, the tree height ## SSD Performance Has Advanced Faster Than Cloud Vendor NVMe Instances DevFeed: [SSD Performance Has Advanced Faster Than Cloud Vendor NVMe Instances]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2024-02-19T08:00:00Z Content type: opinion Language: en Sources: [Database Architects]() Topics: [Cloud](), [Amazon EC2](), [NVMe](), [pcie](), [datacenter]() Tags: [aws](), [capacity](), [cloud](), [cost](), [data-center](), [ec2](), [io](), [nvme](), [pcie](), [performance](), [server](), [storage]() ### AI overview The article compares rapid advances in commodity PCIe and NVMe SSD performance with slower progress in cloud-based NVMe instances. It argues that AWS EC2 instance performance per SSD has remained around 2 GB/s since the i3 launch, leaving a substantial gap between leading data center SSDs and those offered by major cloud vendors. ### Source excerpt In recent years, flash-based SSDs have largely replaced disks for most storage use cases. Internally, each SSD consists of many independent flash chips, each of which can be accessed in parallel. Assuming the SSD controller keeps up, the throughput of an SSD therefore primarily depends on the interface speed to the host. In the past six years, we have seen a rapid transition from SATA to PCIe 3.0 to PCIe 4.0 to PCIe 5.0. As a result, there was an explosion in SSD throughput: At the same time, we saw not just better performance, but also more capacity per dollar: The two plots illustrate the power of a commodity market. The combination of open standards (NVMe and PCIe), huge demand, and competing vendors led to great benefits for customers. Today, top PCIe 5.0 data center SSDs such as the Kioxia CM7-R or Samsung PM1743 achieve up to 13 GB/s read throughput and 2.7M+ random read IOPS. Modern servers have around 100 PCIe lanes, making it possible to have a dozen of SSDs (each usually using 4 lanes) in a single server at full bandwidth. For example, in our lab we have a single-socket Zen 4 server with 8 Kioxia CM7-R SSDs, which achieves 100GB/s (!) I/O bandwidth: AWS EC2 was an early NVMe pioneer, launching the i3 instance with 8 physically-attached NVMe SSDs in early 2017. At that time, NVMe SSDs were still expensive, and having 8 in a single server was quite remarkable. The per-SSD read (2 GB/s) and write (1 GB/s) performance was considered state of the art as well. Another step forward occurred in 2019 with the launch of i3en instances, which doubled storage capacity per dollar. Since then, several NVMe instance types, including i4i and im4gn, have been launched. Surprisingly, however, the performance has not increased; seven years after the i3 launch, we are still stuck with 2 GB/s per SSD. Indeed, the venerable i3 and i3en instances basically remain the best EC2 has to offer in terms of IO-bandwidth/$ and SSD-capacity/$, respectively. Personally, I find this very s ## CPU performance improvements have stagnated on a cost-adjusted basis DevFeed: [CPU performance improvements have stagnated on a cost-adjusted basis]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2023-04-09T12:08:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [cpu](), [x86](), [Hardware](), [.NET 9]() Tags: [amd](), [cost](), [cpu](), [intel](), [performance](), [server-cpus](), [x86]() ### AI overview The article examines the slowdown of CPU improvements after Dennard scaling faltered around 2005. Using AMD Epyc data and comparisons with Intel CPUs in EC2, it argues that cost-adjusted gains in cores, performance, and logic transistor counts have largely stagnated, although newer cores still offer better performance. ### Source excerpt For at least five decades, Moore's law consistently delivered increasing numbers of transistors. Equally significant, Dennard scaling led to each transistor using less energy, enabling higher clock frequencies. This was great, as higher clock frequencies enhanced existing software performance automatically, without necessitating any code rewrite. However, around 2005, Dennard scaling began to falter, and clock frequencies have largely plateaued since then. Despite this, Moore's law continued to advance, with the additional available transistors being channeled into creating more cores per chip. The following graph displays the number of cores for the largest available x86 CPU at the time: Notice the logarithmic scale: this represents the exponential trend we had become accustomed to, with core counts doubling roughly every three years. Regrettably, when considering cost per core, this impressive trend appears to have stalled, ushering in an era of CPU stagnation. To demonstrate this stagnation, I gathered data from wikichip.org on AMD's Epyc single-socket CPU lineup, introduced in 2017 and now in its fourth generation (Naples, Rome, Milan, Genoa): Model Gen Launch Cores GHz IPC Price 7351P Naples 06/2017 16 2.4 1.00 $750 7401P Naples 06/2017 24 2.0 1.00 $1,075 7551P Naples 06/2017 32 2.0 1.00 $2,100 7302P Rome 08/2019 16 3.0 1.15 $825 7402P Rome 08/2019 24 2.8 1.15 $1,250 7502P Rome 08/2019 32 2.5 1.15 $2,300 7702P Rome 08/2019 64 2.0 1.15 $4,425 7313P Milan 03/2021 16 3.0 1.37 $913 7443P Milan 03/2021 24 2.9 1.37 $1,337 7543P Milan 03/2021 32 2.8 1.37 $2,730 7713P Milan 03/2021 64 2.0 1.37 $5,010 9354P Genoa 11/2022 32 3.3 1.57 $2,730 9454P Genoa 11/2022 48 2.8 1.57 $4,598 9554P Genoa 11/2022 64 3.1 1.57 $7,104 9654P Genoa 11/2022 96 2.4 1.57 $10,625 Over these past six years, AMD has emerged as the x86 performance per dollar leader. Examining these numbers should provide insight into the state of server CPUs. Let's first observe CPU cores per dollar: This deviates ## Five Decades of Database Research DevFeed: [Five Decades of Database Research]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2023-02-07T14:31:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Database]() Tags: [articles](), [database](), [paper](), [research](), [trends]() ### AI overview An overview of five decades of database research, reporting that more than 24,000 articles have been published in major database venues since 1975. It notes that publication volume is rising and research topics change over time. ### Source excerpt Since 1975, over 24 thousand articles have have been published in major database venues (SIGMOD, VLDB/PVLDB, ICDE, EDBT, CIDR, TODS, VLDB Journal, TKDE). The number of papers per year is rising: Over time, the topics change. Looking at the percentage of keywords appearing in paper titles (in that particular year), we can see interesting trends: ## For systems, research is development and development is research DevFeed: [For systems, research is development and development is research]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2023-01-23T12:13:00Z Content type: opinion Language: en Sources: [Database Architects]() Topics: [systems](), [Databases](), [Development](), [Software](), [DuckDB]() Tags: [database](), [developers](), [development](), [duckdb](), [software](), [systems](), [writing]() ### AI overview This opinion argues that systems research and system development are two sides of the same process. Developers should study existing literature, compare approaches experimentally, invent solutions when needed, and write about their work, while researchers should ground new techniques in real systems and practical problems. ### Source excerpt The Conference on Innovative Data Systems Research (CIDR) 2023 is over, and as usual both the official program and the informal discussions have been great. CIDR encourages innovative, risky, and controversial ideas as well as honest exchanges. One intensely-discussed talk was the keynote by Hannes Mühleisen, who together with Mark Raasveldt is the brain behind DuckDB. In the keynote, Hannes lamented the incentives of systems researchers in academia (e.g., papers over running code). He also criticized the often obscure topics database systems researchers work on while neglecting many practical and pressing problems (e.g., top-k algorithms rather than practically-important issues like strings). Michael Stonebraker has similar thoughts on the database systems community. I share many of these criticisms, but I'm more optimistic regarding what systems research in academia can do, and would therefore like to share my perspective. Software is different: copying it is free, which has two implications: (1) Most systems are somewhat unique -- otherwise one could have used an existing one. (2) The cost of software is dominated by development effort. I argue that, together, these two observations mean that systems research and system development are two sides of the same coin. Because developing complex systems is difficult, reinventing the wheel is not a good idea -- it's much better to stand on the proverbial shoulders of giants. Thus, developers should look at the existing literature to find out what others have done, and should experimentally compare existing approaches. Often there are no good solutions for some problems, requiring new inventions, which need to be written up to communicate them to others. Writing will not just allow communication, it will also improve conceptual clarity and understanding, leading to better software. Of course, all these activities (literature review, experiments, invention, writing) are indistinguishable from systems research. On the othe ## Making unwinding through JIT-ed code scalable - b-tree operations DevFeed: [Making unwinding through JIT-ed code scalable - b-tree operations]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2022-06-26T09:00:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Algorithms](), [Code](), [Programming](), [JIT]() Tags: [algorithms](), [article](), [code](), [complexity](), [jit](), [locking]() ### AI overview This article explains high-level B-tree insertion and deletion algorithms in a series about scalable unwinding through JIT-ed code. It describes eager splitting of full nodes during insertion to simplify top-to-bottom locking, and merging or balancing nodes during deletion to preserve occupancy and avoid upward propagation. ### Source excerpt This article is part of the series about scalable unwinding that starts here. Now that we have all infrastructure in place, we look at the high-level algorithms. For inserts, we walk down the tree until we hit the leaf-node that should contain the new value. If that node is full, we split the leaf node, and insert a new separator into the parent node to distinguish the two nodes. To avoid propagating that split further up (as the inner node might be full, too, requiring an inner split), we eagerly split full inner nodes when walking down. This guarantees that the parent of a node is never full, which allows us to look at nodes purely from top-to-bottom, which greatly simplifies locking. The splits themselves are relatively simple, we just copy the right half of each node into a new node, reduce the size of the original node, and insert a separator into the parent. However two problems require some care 1) we might have to split the root, which does not have a parent itself, and 2) the node split could mean that the value we try to insert could be either in the left or the right node. The split functions always update the node iterator to the correct node, and release the lock on the node that is not needed after the split. // Insert a new separator after splitting static void btree_node_update_separator_after_split (struct btree_node *n, uintptr_t old_separator, uintptr_t new_separator, struct btree_node *new_right) { unsigned slot = btree_node_find_inner_slot (n, old_separator); for (unsigned index = n->entry_count; index > slot; --index) n->content.children[index] = n->content.children[index - 1]; n->content.children[slot].separator = new_separator; n->content.children[slot + 1].child = new_right; n->entry_count++; } // Check if we are splitting the root static void btree_handle_root_split (struct btree *t, struct btree_node **node, struct btree_node **parent) { // We want to keep the root pointer stable to allow for contention // free reads. Thus, we split the ro ## Making unwinding through JIT-ed code scalable - The b-tree DevFeed: [Making unwinding through JIT-ed code scalable - The b-tree]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2022-06-26T08:56:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Data structures](), [Concurrency](), [Concurrent Programming](), [Code]() Tags: [code](), [data-structure](), [implementation](), [memory](), [node](), [object](), [recursion](), [structure](), [synchronization]() ### AI overview This article explains the data-structure and infrastructure portions of a scalable unwinding system that uses a B-tree for fast lookup and data locality. It describes node organization, invariants, fence keys, helper functions, optimistic lock coupling, memory reclamation through a free list, and recursive destruction; insert, remove, and lookup operations are deferred to the next article. ### Source excerpt This article is part of the series about scalable unwinding that starts here. We use a b-tree because it offers fast lookup, good data locality, and a scalable implementation is reasonable easy when using optimistic lock coupling. Nevertheless a b-tree is a non-trivial data structure. To avoid having one huge article that includes all details of the b-tree, we just discuss the data structure themselves and some helper functions here, the insert/remove/lookup operations will be discussed in the next article. A b-tree partitions its elements by value. An inner node contains a sorted list of separator/child pairs, with the guarantee that the elements in the sub-tree rooted at the child pointer will be <= the separator. The leaf nodes contains sorted lists of (base, size, object) entries, where the object is responsible for unwinding entries between base and base+size. An b-tree maintains the invariants that 1) all nodes except the root are at least half full, and 2) a leaf nodes have the same distance to the root. This guarantees us logarithmic lookup costs. Note that we use fence-keys, i.e., the inner nodes have a separator for the right-most entries, too, which is not the case in all b-tree implementations: // The largest possible separator value static const uintptr_t max_separator = ~((uintptr_t) (0)); // Inner entry. The child tree contains all entries <= separator struct inner_entry { uintptr_t separator; struct btree_node *child; }; // Leaf entry. Stores an object entry struct leaf_entry { uintptr_t base, size; struct object *ob; }; // node types enum node_type { btree_node_inner, btree_node_leaf, btree_node_free }; // Node sizes. Chosen such that the result size is roughly 256 bytes #define max_fanout_inner 15 #define max_fanout_leaf 10 // A btree node struct btree_node { // The version lock used for optimistic lock coupling struct version_lock version_lock; // The number of entries unsigned entry_count; // The type enum node_type type; // The payload union { / ## Making unwinding through JIT-ed code scalable - Optimistic Lock Coupling DevFeed: [Making unwinding through JIT-ed code scalable - Optimistic Lock Coupling]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2022-06-26T08:52:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Exception](), [Data structures](), [Concurrency]() Tags: [code](), [data-structure](), [exception](), [exception-handling](), [locking](), [mutex](), [performance](), [set]() ### AI overview The article explains a scalable approach to unwinding through JIT-ed code using a read-optimized B-tree with optimistic lock coupling. Writers use conventional exclusive lock coupling, while readers use version locks and validate their reads so they can run in parallel when writes are uncommon. ### Source excerpt This article is part of the series about scalable unwinding that starts here. When thinking about exception handling it is reasonable to assume that we will have far more unwinding requests than changes to the unwinding tables. In our setup, the tables only change when JITed code is added to or removed from the program. That is always expensive to begin with due the mprotect calls, TLB shootdowns, etc. Thus we can safely assume that we will have at most a few hundred updates per second even in extreme cases, probably far less. Lookups however can easily reach thousands or even millions per second, as we do one lookup per frame. This motivates us to use a read-optimized data structure, a b-tree with optimistic lock coupling: Writers use traditional lock coupling (lock parent node exclusive, lock child node exclusive, release parent node, lock child of child, etc.), which works fine as long as there is not too much contention. Readers however have to do something else, as we expect thousands of them. One might be tempted to use a rw-lock for readers, but that does not help. Locking an rw-lock in shared mode causes an atomic write, which makes the threads fight over the cache line of the lock even if there is no (logical) contention. Instead, we use version locks, where readers do no write at all: // Common logic for version locks struct version_lock { // The lock itself. The lowest bit indicates an exclusive lock, // the second bit indicates waiting threads. All other bits are // used as counter to recognize changes. // Overflows are okay here, we must only prevent overflow to the // same value within one lock_optimistic/validate // range. Even on 32 bit platforms that would require 1 billion // frame registrations within the time span of a few assembler // instructions. uintptr_t version_lock; }; #ifdef __GTHREAD_HAS_COND // We should never get contention within the tree as it rarely changes. // But if we ever do get contention we use these for waiting static __gthre ## Making unwinding through JIT-ed code scalable - Replacing the gcc hooks DevFeed: [Making unwinding through JIT-ed code scalable - Replacing the gcc hooks]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2022-06-26T08:48:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [gcc](), [patches](), [JIT]() Tags: [atomic](), [gcc](), [jit](), [lock-free](), [mutex](), [patches]() ### AI overview This article explains patches to GCC that replace a globally locked list of unwinding frames with a read-optimized B-tree. The change enables concurrent registration, deregistration, and lock-free lookups, while keeping frames immutable during unwinding on platforms that support atomics. ### Source excerpt This article is part of the series about scalable unwinding that starts here. As discussed in the previous article, the gcc mechanism does not scale because it uses a global lock to protect its list of unwinding frames. To solve that problem, we replace that list with a read-optimized b-tree that allows for concurrent reads and writes. In this article we just discuss the patches to gcc necessary to enable that mechanism, the b-tree itself is discussed in subsequent articles. We start by replacing the old fast path mechanism with a b-tree root: index 8ee55be5675..d546b9e4c43 100644 --- a/libgcc/unwind-dw2-fde.c +++ b/libgcc/unwind-dw2-fde.c @@ -42,15 +42,34 @@ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see #endif #endif +#ifdef ATOMIC_FDE_FAST_PATH +#include "unwind-dw2-btree.h" + +static struct btree registered_frames; + +static void +release_registered_frames (void) __attribute__ ((destructor (110))); +static void +release_registered_frames (void) +{ + /* Release the b-tree and all frames. Frame releases that happen later are + * silently ignored */ + btree_destroy (®istered_frames); +} + +static void +get_pc_range (const struct object *ob, uintptr_t *range); +static void +init_object (struct object *ob); + +#else + /* The unseen_objects list contains objects that have been registered but not yet categorized in any way. The seen_objects list has had its pc_begin and count fields initialized at minimum, and is sorted by decreasing value of pc_begin. */ static struct object *unseen_objects; static struct object *seen_objects; -#ifdef ATOMIC_FDE_FAST_PATH -static int any_objects_registered; -#endif #ifdef __GTHREAD_MUTEX_INIT static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT; @@ -78,6 +97,7 @@ init_object_mutex_once (void) static __gthread_mutex_t object_mutex; #endif #endif +#endif When the platform supports atomics (ATOMIC_FDE_FAST_PATH), we replace the whole mechanism with one b-tree, whose root is registered_frames. Neither the ## Making unwinding through JIT-ed code scalable DevFeed: [Making unwinding through JIT-ed code scalable]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2022-06-26T08:46:00Z Content type: tutorial Language: en Sources: [Database Architects]() Topics: [C++](), [Exception](), [gcc](), [Concurrency](), [Jule](), [systems]() Tags: [c-plus-plus](), [compiler](), [concurrent](), [exception](), [gcc](), [hooks](), [jit](), [lock-free](), [mutex](), [series]() ### AI overview This article explains why C++ exception unwinding remains effectively single-threaded when JIT-ed code is registered. It describes limitations in gcc and glibc mechanisms and introduces a gcc patch using a read-optimized lock-free b-tree to support parallel unwinding without atomic writes. ### Source excerpt Exceptions are a very handy mechanism to propagate errors in C++ programs, but unfortunately they do not scale very well. In all common C++ implementations the unwinding mechanism takes global lock during unwinding, which has disastrous consequences when the number of threads is high. On a machine with 256 hardware context we see worse-than-single-threaded behavior even for relatively modest failure rates. Fortunately the Florian Weimer fixed one contention point in gcc 12 on systems with glibc 2.35 or newer, which gives us scalable exceptions as long as no JIT-ed code has been registered. Unfortunately our system does register JIT-ed code... Which means exception unwinding in our code base is still single-threaded in practice. But we can fix that by teaching gcc to store the unwinding information in a read-optimized b-tree, which allows for fully parallel unwinding without any atomic writes. There is a gcc patch that does just that, but unfortunately it is quite involved and difficult to review. This article series thus explains all parts of the patch and shows how a read-optimized b-tree can be implemented lock-free. In order to keep the article length somewhat reasonable, the discusses is broken into parts: The problem (this article) Replacing the gcc hooks Optimistic Lock Coupling The b-tree b-tree operations When unwinding exceptions, the compiler has to find the corresponding unwinding information for every call frame on the stack between the throw and the catch. gcc uses two different mechanisms for that: For ahead-of-time compiled code it asks glibc to find the unwinding information using either dl_iterate_phdr (on older systems) or _dl_find_object (on systems with glibc 2.35 or newer). Note that this mapping is not static, as shared libraries could be added or removed at any time, potentially during a concurrent unwind. For that reason dl_iterate_phdr was protected by a global mutex, which clearly does not scale. _dl_find_object avoids that mutex by using a ## Cloud Network Traffic Within the Same Region Can Be Very Expensive DevFeed: [Cloud Network Traffic Within the Same Region Can Be Very Expensive]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2022-04-03T07:59:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Amazon Web Services](), [Cloud](), [Amazon EC2](), [Amazon S3](), [Availability](), [Network]() Tags: [amazon-ec2](), [amazon-s3](), [availability](), [aws](), [cloud](), [cost](), [ipv4](), [storage]() ### AI overview The article examines AWS network transfer costs within a single region, explaining that EC2 traffic between Availability Zones is charged in both directions. It describes using Amazon S3 as an intermediary to reduce the cost of moving data between Availability Zones. ### Source excerpt Everyone knows that the major cloud vendors try to make it easy to get data in, and hard to get it out. What is less known is that high egress cost also applies to outbound traffic within the same region. Let's look at AWS specifically. In AWS, EC2 outbound traffic is only free within the same availability zone (AZ). Moving data from one AZ to another in the same region is actually quite expensive: "IPv4: Data transferred "in" to and "out" from Amazon EC2 [...] across Availability Zones in the same AWS Region is charged at $0.01/GB in each direction." source This means that transferring 1TB costs $0.01/GB * 1000GB * 2 = $20. For comparison: most inter-region transfers cost $0.02 per GB, but only for outgoing traffic. Thus, remarkably, transferring 1TB from Ohio to Tokyo will cost the same as transferring it within Ohio from us-east-2a to us-east-2b. Two c5n.18xlarge instances communicating with each other at full 100 Gbit speed can theoretically incur network costs of $1,800 per hour (or $1,296,000 per month). Interestingly, S3 can be used to bypass the high traffic cost when moving data between different AZs in the same region because "Data transferred directly between Amazon S3 [...] in the same AWS Region is free." source Let's see if we can exploit this. Consider again our example where we want to transfer 1TB from us-east-2a to us-east-2b. Instead of two EC2 instances talking directly, we could use an S3 Standard bucket in us-east-2. We first PUT the data into it from us-east-2a, then GET the data from that bucket using us-east-2b instances, and finally delete all objects. If we split our data into 1,000 1GB chunks, we need to pay for only 1,000 PUT and 1,000 GET S3 requests, which would be less than $0.01. Storage cost is also low: assuming a transfer rate of 1GB/s, the data would have to be stored in S3 for less than an hour, which costs about $0.03 (and could be reduced via pipelining). Thus, in total we can transfer 1TB through S3 for less than $0.05 instea ## Are you sure you want to use MMAP in your database management system? DevFeed: [Are you sure you want to use MMAP in your database management system?]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2022-01-16T14:07:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Databases](), [Caching](), [Transactions](), [IO](), [systems](), [Kernel](), [NVMe]() Tags: [asynchronous](), [cache](), [caching](), [database](), [kernel](), [nvme](), [pcie](), [performance](), [systems](), [transactions]() ### AI overview The article discusses why database management systems often avoid mmap despite operating-system page caching. It explains that mmap limits control over write-back, transactions, crash recovery, asynchronous I/O, and error handling, and argues that Linux page-cache behavior may not keep pace with modern NVMe storage bandwidth. ### Source excerpt Many database management systems carefully manage disk I/O operations and explicitly cache pages in main memory. Operating systems implement a page cache to speed up recurring disk accesses as well, and even allow transparent access to disk files through the mmap system call. Why do most database systems then even implement I/O handling and a caching component if the OS provides these features through mmap? Andrew Pavlo, Andrew Crotty, and myself tried to answer this question in a CIDR 2022 paper. This is quite a contentious question as the Hacker News discussion of the paper shows. The paper argues that using mmap in database systems is almost always a bad idea. To implement transactions and crash recovery with mmap, the DBMS has to write any change out-of-place because there is no way to prevent write back of a particular page. This makes it impossible to implement classical ARIES-style transactions. Furthermore, data access through mmap can take a handful of nanoseconds (if the data is in the CPU cache) or milliseconds (if it's on disk). If a page is not cached, it will be read through a synchronous page fault and there is no interface for asynchronous I/O. I/O errors, on the other hand, are communicated through signals rather than a local error code. These problems are caused by mmap's interface, which is too high-level and does not give the database system enough control. In addition to discussing these interface problems, the paper also shows that Linux' page cache and mmap implementation cannot achieve the bandwidth of modern storage devices. One PCIe 4.0 NVMe SSD can read over 6 GB/s and upcoming PCIe 5.0 SSDs will almost double this number. To achieve this performance, one needs to schedule hundreds or even thousands (if one has multiple SSDs) of concurrent I/O requests. Doing this in a synchronous fashion by starting hundreds of threads will not work well. Other kernel-level performance issues are single-threaded page eviction and TLB shootdowns. Overall, ## AWS EC2 Hardware Trends: 2015-2021 DevFeed: [AWS EC2 Hardware Trends: 2015-2021]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2021-07-04T14:23:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Amazon EC2](), [Hardware](), [Amazon Web Services](), [cpu](), [intel](), [Network](), [NVMe](), [Cloud]() Tags: [aws](), [capacity](), [compute](), [cost](), [cpu](), [ec2](), [hardware](), [intel](), [network](), [nvme]() ### AI overview This article analyzes AWS EC2 hardware trends from 2015 to 2021 using hardware resources normalized by instance price. It finds that compute and DRAM costs changed little, while storage and network bandwidth saw significant improvements. ### Source excerpt Over the past decade, AWS EC2 has introduced many new instance types with different hardware configurations and prices. This hardware zoo can make it hard to keep track of what is available. In this post we will look at how the EC2 hardware landscape changed since 2015. This will hopefully help picking the best option for a given task. In the cloud, one can trade money for hardware resources. It therefore makes sense to take an economical perspective and normalize the hardware resource by the instance price. For example, instead of looking at absolute network bandwidth, we will use network bandwidth per dollar. Such metrics also allow us to ignore virtualized slices, reducing the number of instances relevant for the analysis from hundreds to dozens. For example, c5n.9xlarge is a virtualized slice of c5n.18xlarge with half the network bandwidth and half the cost. Data Set We use historical data from https://instances.vantage.sh/ and only consider current-generation Intel machines without GPUs. All prices are for us-east-1 Linux instances. Using these constraints, in July 2021 we can pick from the following instances: namevCPUmemory [GB]network [Gbit/s]storageprice [$/h]m4.16x6425625 3.20h1.16x64256258x2TB disk3.74c5n.18x72192100 3.89d3.8x322562524x2TB disk4.00c5.24x9619225 4.08r4.16x6448825 4.26m5.24x9638425 4.61c5d.24x96192254x0.9TB NVMe4.61i3.16x64488258x1.9TB NVMe5.00m5d.24x96384254x0.9TB NVMe5.42d2.8x362441024x2TB disk5.52m5n.24x96384100 5.71r5.24x9676825 6.05d3en.12x481927524x14TB disk6.31m5dn.24x963841004x0.9TB NVMe6.52r5d.24x96768254x0.9TB NVMe6.91r5n.24x96768100 7.15r5b.24x9676825 7.15r5dn.24x967681004x0.9TB NVMe8.02i3en.24x967681008x7.5TB NVMe10.85x1e.32x1283904252x1.9TB SATA26.69 && Compute Using our six-year data set, let's first look at the cost of compute: It is quite remarkable that from 2015 to 2021, the cost of compute barely changed. During that six-year time frame, the number of server CPU cores has been growing significantly, which may imply that I ## What Every Programmer Should Know About SSDs DevFeed: [What Every Programmer Should Know About SSDs]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2021-06-18T11:52:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Hardware](), [IO](), [Latency](), [Filesystems](), [io\_uring]() Tags: [asynchronous](), [hardware](), [io](), [io-uring](), [parallelism](), [performance](), [ssd](), [storage]() ### AI overview This article explains how NAND-flash SSDs differ from magnetic disks and how those differences affect software performance. It covers lower random-read latency, internal parallelism, concurrent I/O, and the effect of volatile write caching on observed write latency. ### Source excerpt Solid-State Drives (SSDs) based on flash have largely replaced magnetic disks as the standard storage medium. From the perspective of a programmer, SSDs and disks look very similar: both are persistent, enable page-based (e.g., 4KB) access through file systems and system calls, and have large capacities. However, there are also important differences, which become important if one wants to achieve optimal SSD performance. As we will see, SSDs are more complicated and their performance behavior can appear quite mysterious if one simply thinks of them as fast disks. The goal of this post is to provide an understanding of why SSDs behave the way they do, which can help creating software that is capable of exploiting them. (Note that I discuss NAND flash, not Intel Optane memory, which has different characteristics.) Drives not Disks SSDs are often referred to as disks, but this is misleading as they store data on semiconductors instead of a mechanical disk. To read or write from a random block, a disk has to mechanically move its head to the right location, which takes on the order of 10ms. A random read from an SSD, in contrast, takes about 100us - 100 times faster. This low read latency is the reason why booting from an SSD is so much faster than booting from a disk. Parallelism Another important difference between disks and SSDs is that disks have one disk head and perform well only for sequential accesses. SSDs, in contrast, consist of dozens or even hundreds of flash chips ("parallel units"), which can be accessed concurrently. SSDs transparently stripe larger files across the flash chips at page granularity, and a hardware prefetcher ensures that sequential scans exploit all available flash chips. However, at the flash level there is not much difference between sequential and random reads. Indeed, for most SSDs it is possible to achieve almost the full bandwidth with random page reads as well. To do this, one has to schedule hundreds of random IO requests concurre ## Taming Deep Recursion DevFeed: [Taming Deep Recursion]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2020-11-22T16:50:00Z Content type: tutorial Language: en Sources: [Database Architects]() Topics: [Data structures](), [SQL](), [Parser](), [Code](), [Exception](), [Compiler]() Tags: [code](), [compiler](), [crash](), [data-structures](), [exception](), [recursion](), [snippet](), [sql]() ### AI overview The article examines stack overflows caused by recursive traversal of very deep SQL expression and algebra trees. It discusses stack-usage checks, explicit-stack iteration, and compiler-supported split stacks as ways to handle unusually deep inputs while preserving simpler recursive code. ### Source excerpt When operating on hierarchical data structures, it is often convenient to formulate that using pairwise recursive functions. For example, our semantic analysis walks that parse tree recursively and transforms it into an expression tree. This corresponding code looks roughly like this: unique_ptr analyzeExpression(AST* astNode) { switch (astNode->getType()) { case AST::BinaryExpression: return analyzeBinaryExpression(astNode->as()); case AST::CaseExpression: return analyzeCaseExpression(astNode->as()); ... } } unique_ptr analyzeBinaryExpression(BinaryExpAST* astNode) { auto left = analyzeExpression(astNode->left); auto right = analyzeExpression(astNode->right); auto type = inferBinaryType(astNode->getOp(), left, right); return make_unique(astNode->getOp(), move(left), move(right), type); } It recursively walks the tree, collects input expressions, infers types, and constructs new expressions. This works beautifully until you encounter a (generated) query with 300,000 expressions, which we did. At that point our program crashed due to stack overflow. Oops. Our first mitigation was using __builtin_frame_address(0) at the beginning of analyzeExpression to detect excessive stack usage, and to throw an exception if that happens. This prevented the crash, but is not very satisfying. First, it means we refuse a perfectly valid SQL query "just" because it uses 300,000 terms in one expression. And second, we cannot be sure that this is enough. There are several places in the code that recursively walk the algebra tree, and it is hard to predict their stack usage. Even worse, the depth of the tree can change due to optimizations. For example, when a query has 100,000 entries in the from clause, the initial tree is extremely wide but flat. Later, after we have stopped checking for stack overflows, the optimizer might transform that into a tree with 100,000 levels, again leading to stack overflow. Basically, all ## C++ Concurrency Model on x86 for Dummies DevFeed: [C++ Concurrency Model on x86 for Dummies]() Original publisher: [Read original article]() Author: Viktor Leis (noreply@blogger.com) Published: 2020-10-30T16:17:00Z Content type: tutorial Language: en Sources: [Database Architects]() Topics: [C++](), [Concurrency](), [x86](), [Compiler](), [Data structures]() Tags: [atomic](), [c-plus-plus](), [code](), [compiler](), [concurrency](), [data-structures](), [x86]() ### AI overview This tutorial explains a practical subset of the C++11 memory model for writing high-performance concurrent code on x86. It emphasizes using std::atomic, choosing memory orders, and avoiding undefined behavior from data races, while noting that the simplified approach may be less efficient on non-x86 platforms such as ARM. ### Source excerpt Since C++11, multi-threaded C++ code has been governed by a rigorous memory model. The model allows implementing concurrent code such as low-level synchronization primitives or lock-free data structures in a portable fashion. To use the memory model, programmers need to do two things: First, they have to use the std::atomic type for concurrently-accessed memory locations. Second, each atomic operation requires a memory order argument with six options determining the concurrency semantics in terms of which re-orderings are allowed. (Some operations even allow specifying two memory orders!) While there are a number of attempts to describe the model, I always found the full semantics very hard to understand and consequently concurrent code hard to write and reason about. And since we are talking about low-level concurrent code here, making a mistake (like picking the wrong memory order) can lead to disastrous consequences. Luckily, at least on x86, a small subset of the full C++11 memory model is sufficient. In this post, I'll present such a subset that is sufficient to write high-performance concurrent code on x86. This simplification has the advantage that the resulting code is much more likely to be correct, without leaving any performance on the table. (On non-x86 platforms like ARM, code written based on this simplified model will still be correct, but might potentially be slightly slower than necessary.) There are only six things one needs to know to write high-performance concurrent code on x86. 1. Data races are undefined If a data race occurs in C++, the behavior of the program is undefined. Let's unpack that statement. A data race can be defined as two or more threads accessing the same memory location with at least one of the accesses being a write. By default (i.e., without using std::atomic), the compiler may assume that no other thread is concurrently modifying memory. This allows the compiler to optimize the code, for example by reordering or optimizing ## Linear Time Liveness Analysis DevFeed: [Linear Time Liveness Analysis]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2020-04-28T14:42:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Compiler](), [Code](), [gcc](), [C]() Tags: [analysis](), [c](), [code](), [compilation](), [compiler](), [compilers](), [cpp](), [gcc]() ### AI overview The article examines why compilers can take super-linear time on large generated functions with many conditional blocks. It reports that GCC becomes effectively unable to compile sufficiently large examples and that Clang also shows super-linear behavior under optimization. It then introduces a control-flow-graph-based approach to liveness analysis intended to scale better than propagating liveness sets. ### Source excerpt Standard compiler are usually used with hand-written programs. These programs tend to have reasonably small functions, and can be processed in (nearly) linear time. Generated programs however can be quite large, and compilers sometimes struggle to compile them at all. This can be seen with the following (silly) demonstration script: import subprocess from timeit import default_timer as timer def doTest(size): with open("foo.cpp", "w") as out: print("int foo(int x) {", file=out) for s in range(size): p="x" if s==0 else f'l{s-1}' print (f'int l{s}; if (__builtin_sadd_overflow({p},1,&l{s})) goto error;', file=out) print(f'return l{size-1};error: throw;}}', file=out); start = timer() subprocess.run(["gcc", "-c", "foo.cpp"]) stop = timer() print(size, ": ", (stop-start)) for size in [10,100,1000,10000,100000]: doTest(size) It generates one function with n statements of the form "int lX; if (__builtin_sadd_overflow(lY,1,&lX)) goto error;" which are basically just n additions with overflow checks, and then measures the compile time. The generated code is conceptually a very simple, but it contains a lot of basic blocks due to the large number of ifs. When compiling with gcc we get the following compile times: n101001,00010,000100,000 compilation [s]0.020.040.1934.99> 1h The compile time is dramatically super linear, gcc is basically unable to compile the function if it contains 10,000 ifs or more. In this simple example clang fares better when using -O0, but with -O1 it shows super-linear compile times, too. This is disastrous when processing generated code, where we cannot easily limit the size of individual functions. In our own system we use neither gcc nor clang for query compilation, but we have same problem, namely compiling large generated code. And super-linear runtime quickly becomes an issue when the input is large. One particular important problem in this context is liveness analysis, i.e, figuring out which value is alive at which part of the program. The textb ## All hash table sizes you will ever need DevFeed: [All hash table sizes you will ever need]() Original publisher: [Read original article]() Author: Thomas Neumann (noreply@blogger.com) Published: 2020-01-30T13:19:00Z Content type: article Language: en Sources: [Database Architects]() Topics: [Code](), [Cache]() Tags: [cache](), [code](), [hash](), [map](), [performance]() ### AI overview This technical blog post explains how to choose hash table sizes using precomputed prime numbers and Hacker's Delight magic numbers. The approach replaces costly modulo operations with multiplications and reports benchmark results on an AMD 1950X. ### Source excerpt When picking a hash table size we usually have two choices: Either, we pick a prime number or a power of 2. Powers of 2 are easy to use, as a modulo by a power of 2 is just a bit-wise and, but 1) they waste quite a bit of space, as we have to round up to the next power of 2, and 2) they require "good" hash functions, where looking at just a subset of bits is ok. Prime numbers are more forgiving concerning the hash function, and we have more choices concerning the size, which leads to less overhead. But using a prime number requires a modulo computation, which is expensive. And we have to find a suitable prime number at runtime, which is not that simple either. Fortunately we can solve both problems simultaneously, which is what this blog post is about. We can tackle the problem of finding prime numbers by pre-computing suitable numbers with a given maximum distance. For example when when only considering prime numbers that are at least 5% away from each other we can cover the whole space from 0 to 2^64 with just 841 prime numbers. We can solve the performance problem by pre-computing the magic numbers from Hacker's Delight for each prime number in our list, which allows us to use multiplications instead of expensive modulo computations. And we can skip prime numbers with unpleasant magic numbers (i.e., the ones that require an additional add fixup), preferring the next cheap prime number instead. The resulting code can be found here. It contains every prime number you will ever need for hash tables, covering the whole 64bit address space. Usage is very simple, we just ask for a prime number and then perform modulo operations as needed: class HashTable { primes::Prime prime; vector table; public: HashTable(uint64_t size) { prime = prime::Prime::pick(size); table.resize(prime.get()); } ... Entry* getEntry(uint64_t hash) { return table[prime.mod(hash)]; } ... }; The performance is quite good. On an AMD 1950X, computing the modulo for 10M values (and computing the sum o