HNHacker News
TopNewBestAskShowJobs

matt_d

22,061 karma · joined April 21, 2014

submissionscomments
matt_d··on The Ethical Compiler: Addressing the Is-Ought Gap in Compilation (PEPM 2025) [video]
Preprint: https://williamjbowman.com/resources/wjb2024-ethical-compile...

DOI: https://doi.org/10.1145/3704253.3706135

William J. Bowman. The 2025 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM) – Invited Talk.

Abstract:

"The is-ought gap is a problem in moral philosophy observing that ethical judgments ("ought") cannot be grounded purely in truth judgments ("is"): that an ought cannot be derived from an is.

This gap renders the following argument invalid: "It is true that type safe languages prevent bugs and that bugs cause harm, therefore you ought to write in type safe languages".

To validate ethical claims, we must bridge the gap between is and ought with some ethical axiom, such as "I believe one ought not cause harm".

But what do ethics have to do with manipulating programs?

A lot!

Ethics are central to correctness!

For example, suppose an algorithm infers the type of is Bool, and is in fact a Bool; the program type checks.

Is the program correct-does it behave as it ought?

We cannot answer this without some ethical axioms: what does the programmer believe ought to be?

I believe one ought to design and implement languages ethically.

We must give the programmer the ability to express their ethics-their values and beliefs about a program-in addition to mere computational content, and build tools that respect the distinction between is and ought.

This paper is a guide to ethical language design and implementation possibilities."

matt_d··on How to Make the Most Out of SIMD on AArch64?
3-min talk: https://www.youtube.com/watch?v=791PEI35tio

Abstract:

> Interleaving/Unrolling and Vectorization are two popular means to optimize applications. While the first one creates multiple copies of the loop body content, the second one focuses on operating on multiple data elements in parallel thanks to SIMD units available in the CPU. In theory, interleaving and vectorization are orthogonal optimizations, one relying on instruction-level parallelism/superscalarity, and the other on data-level parallelism within a single instruction. Modern CPU architectures provide both of these parallelism mechanisms at once, and the combination of vectorization and interleaving is complex, influencing each other due to instruction selection and complexity of underlying hardware, and the programmer often has to rely on the compiler's auto-vectorization.

> Based on a large evaluation of 642 loops coming from the literature, this paper demonstrates that significant gains (up to 20%) can be obtained by adapting the LLVM auto-vectorizer to better exploit interleaving and vectorization for a given AArch64 architecture. The proposed approach is flexible and can be easily applied at both loop level or application level. Experiments on 5 mini-apps coming from the HPC realm show similar improvements and demonstrates the co-design potential of the presented approach.

matt_d··on The Cost of Garbage Collection for State Machine Replication
Abstract: https://arxiv.org/abs/2405.11182

PDF: https://arxiv.org/pdf/2405.11182

Section 8, Conclusion:

    In this paper, we quantify the overhead of running a state machine replication system for cloud systems written in a language with GC. To this end, we (1) design from scratch a canonical cloud system—a distributed, consensus-based, linearizable key-values store, (2) implement it in C++, Java, Rust, and Go, (3) evaluate implementations under an update-heavy and read-heavy workloads on AWS under different resource constraints while trying to hit the maximum throughput with a fixed low tail latency. Our results show that even with ample memory, GC has a non-trivial cost, and with limited memory, languages with memory management can achieve an order of magnitude higher throughput than the languages with GC on the same hardware. Our key observation is that if a cloud system is expected to grow to a large volume of users, building the system in a language with manual memory management and thereby paying a higher development cost than using a language with GC may result in a significant cloud cost savings in the long run.
matt_d··on Ways to generate SSA
On that note, there's an ongoing discussion on allowing early exits currently not allowed in the MLIR's SCF (structured control flow) dialect, https://discourse.llvm.org/t/rfc-region-based-control-flow-w..., https://github.com/google/heir/issues/922
matt_d··on Compiler Fuzzing in Continuous Integration: A Case Study on Dafny [pdf]
Abstract:

"We present the design of CompFuzzCI, a framework for incorporating compiler fuzzing into the continuous integration (CI) workflow of the compiler for Dafny, an open-source programming language that is increasingly used in and contributed to by industry. CompFuzzCI explores the idea of running a brief fuzzing campaign as part of the CI workflow of each pull request to a compiler project. Making this effective involved devising solutions for various challenges, including how to deduplicate bugs, how to bisect the project’s revision history to find the commit responsible for a regression (challenging when project interfaces change over time), and how to ensure that fuzz testing complements existing regression testing efforts. We explain how we have engaged with the Dafny development team at Amazon to approach these and other problems in the design of CompFuzzCI, and the lessons learned in the process. As a by-product of our work with CompFuzzCI, we found and reported three previously-unknown bugs in the Dafny compiler. We also present a controlled experiment simulating the use of CompFuzzCI over time on a range of Dafny commits, to assess its ability to find historic bugs. CompFuzzCI prioritises support for the Dafny compiler and the fuzz-d fuzzer but has a generalisable design: with modest modification to its internal interfaces, it could be adapted to work with other fuzzers, and the lessons learned from our experience will be relevant to teams considering including fuzzing in the CI of other industrial software projects."

https://github.com/CompFuzzCI

matt_d··on The Fuzzing Book
More on compiler correctness in general: https://github.com/MattPD/cpplinks/blob/master/compilers.cor... and fuzzing in particular: https://github.com/MattPD/cpplinks/blob/master/compilers.cor...
matt_d··on CMU 15-799: Special Topics in Databases: Query Optimization (Spring 2025)
Schedule (with readings & lectures): https://15799.courses.cs.cmu.edu/spring2025/schedule.html

Lectures YouTube Playlist: https://www.youtube.com/playlist?list=PLSE8ODhjZXjYCZfIbmEWH...

Announcement: https://discuss.systems/@andy_pavlo/113839208543526204

"New @CMUDB Course: Database Query Optimization

This is a special topics course on how to build a SQL optimizer from scratch covering foundational and state-of-the-art implementations. All lectures available on Youtube: https://15799.courses.cs.cmu.edu/spring2025/

One topic we will discuss is the Cascades optimizer architecture. There has never been a good description of how to implement it but the Microsoft Research Database Group just published a book that describes SQL Server's implementation. Microsoft has made the entire book available for free: https://www.microsoft.com/en-us/research/publication/extensi...

Query optimization is the hardest topic in databases and this is the first time I am offering this course. I am going to make mistakes and say incorrect things in my lectures. Send corrections to db-mistakes@cs.cmu.edu"

matt_d··on Property-Based Testing for the People
Right, metamorphic testing in particular (which would be a special case of PBT, with metamorphic relations being properties), https://en.wikipedia.org/wiki/Metamorphic_testing, https://github.com/MattPD/cpplinks/blob/master/testing.md#pr...

One simple example (from the above) is "sin (π − x) = sin x" for the implementation of the sine function not requiring the knowledge of its specific output values. Naturally, instead of the literal equality "=" one can use a more appropriate accuracy specification as in, say, relative ulp (https://en.wikipedia.org/wiki/Unit_in_the_last_place) error bound, cf. https://members.loria.fr/PZimmermann/papers/accuracy.pdf

matt_d··on Snapshottable Stores
Abstract:

"We say that an imperative data structure is snapshottable or supports snapshots if we can efficiently capture its current state, and restore a previously captured state to become the current state again. This is useful, for example, to implement backtracking search processes that update the data structure during search.

Inspired by a data structure proposed in 1978 by Baker, we present a snapshottable store, a bag of mutable references that supports snapshots. Instead of capturing and restoring an array, we can capture an arbitrary set of references (of any type) and restore all of them at once. This snapshottable store can be used as a building block to support snapshots for arbitrary data structures, by simply replacing all mutable references in the data structure by our store references. We present use-cases of a snapshottable store when implementing type-checkers and automated theorem provers.

Our implementation is designed to provide a very low overhead over normal references, in the common case where the capture/restore operations are infrequent. Read and write in store references are essentially as fast as in plain references in most situations, thanks to a key optimisation we call record elision. In comparison, the common approach of replacing references by integer indices into a persistent map incurs a logarithmic overhead on reads and writes, and sophisticated algorithms typically impose much larger constant factors.

The implementation, which is inspired by Baker’s and the OCaml implementation of persistent arrays by Conchon and Filliâtre, is both fairly short and very hard to understand: it relies on shared mutable state in subtle ways. We provide a mechanized proof of correctness of its core using the Iris framework for the Coq proof assistant."

Motivating example:

"Union-Find is a central data structure in several algorithms. For example, it is at the core of ML type inference, which proceeds by repeated unification between type variables. Union-Find can also be used to track equalities between type constructors, as introduced in the typing environment when type-checking Guarded Algebraic Data Types (GADTs) for example.

When using a Union-Find data structure to implement a type system, it is common to need backtracking, which requires the inference state to be snapshottable. For example:

(1) A single unification between two types during ML type inference translates into several unifications between type variables, traversing the structure of the two types. If we discover that the two types are in fact incompatible, we fail with a type error. However, we may want to revert the unifications that were already performed, so that the error message shown to the user does not include confusing signs of being halfway through the unification, or so that the interactive toplevel session can continue in a clean environment.

(2) Production languages unfortunately have to consider backtracking to implement certain less principled typing rules: try A, and if it fails revert to a clean state and try B instead.

(3) GADT equations are only added to the typing environment in the context of a given match clause, and must then be rolled back before checking the other clauses.

We have encountered requirements (1) and (2) in the implementation of the OCaml type-checker, and (1) and (3) in the development of Inferno [Pottier, 2014], a prototype type-inference library implemented in OCaml that aims to be efficient.

Now a question for the reader: how would you change the Union-Find implementation above to support snapshots?"

matt_d··on Exploring GPU-to-GPU Communication: Insights into Supercomputer Interconnects
Abstract:

"Multi-GPU nodes are increasingly common in the rapidly evolving landscape of exascale supercomputers. On these systems, GPUs on the same node are connected through dedicated networks, with bandwidths up to a few terabits per second. However, gauging performance expectations and maximizing system efficiency is challenging due to different technologies, design options, and software layers. This paper comprehensively characterizes three supercomputers - Alps, Leonardo, and LUMI - each with a unique architecture and design. We focus on performance evaluation of intra-node and inter-node interconnects on up to 4096 GPUs, using a mix of intra-node and inter-node benchmarks. By analyzing its limitations and opportunities, we aim to offer practical guidance to researchers, system architects, and software developers dealing with multi-GPU supercomputing. Our results show that there is untapped bandwidth, and there are still many opportunities for optimization, ranging from network to software optimization."

Observations:

> Observation 1: Achieving good performance on multi-GPU systems requires non-trivial tuning, which depends on the system, message size, communication library, and number of nodes. The default choices made by *CCL and GPU-Aware MPI are not always optimal, and manual tuning can improve performance up to an order of magnitude.

> Observation 2: GPU-Aware MPI provides the highest goodput for intra-node point-to-point transfers on all the analyzed systems. For small transfers, the optimal solution changes across the systems, depending on architectural features and specific optimization implemented by MPI.

> Observation 3: On LUMI, RCCL point-to-point communication primitives do not correctly determine the bandwidth available between GPUs on the same node, thus underutilizing the available bandwidth.

> Observation 4: For single node collectives, *CCL outperforms GPU-Aware MPI in most cases, except for small collectives on LUMI. Indeed, unlike MPI, *CCL collectives are optimized for the specific GPU models. Nevertheless, there is still room for collective algorithms optimization.

> Observation 5: On inter-node point-to-point communications, MPI outperforms *CCL by up to one order of magnitude on small transfers, and by up to 3x on larger transfers.

> Observation 6: On Alps and LUMI, GPU’s network location has a marginal impact on average performance (below 30% for latency and 1% for goodput). On the other hand, on Leonardo, the average latency increases by up to 2x when the GPUs are in different groups rather than under the same switch. Similarly, the average goodput decreases by 17%. This is mainly due to network performance variability caused by network noise.

> Observation 7: *CCL exploits the intra-node GPU-GPU interconnect more effectively than MPI, being specifically optimized for the target devices. Those advantages are more evident at smaller node counts and for larger transfers, for which the performance of intra-node communications has a higher weight on the overall performance. However, we experienced instability at large node counts for the alltoall on both NCCL and RCCL.

> Observation 8: Network noise decreases the goodput of allreduce and alltoall up to 50%.

*CCL refers to NVIDIA Collective Communications Library (NCCL) and AMD ROCm Collective Communication Library (RCCL)

matt_d··on SIMD Matters: Graph Coloring
For the particularly useful subgraph of topics, see "Notes on Graph Algorithms Used in Optimizing Compilers" by Carl Offner: http://www.cs.umb.edu/~offner/files/flow_graph.pdf

That, and pretty much anything (co)authored by Robert E. Tarjan. I'm serious: https://github.com/search?q=repo%3Allvm%2Fllvm-project%20tar...

There's a good recent survey of the three workhorses: "We survey three algorithms that use depth-first search to find the strong components of a directed graph in linear time: (1) Tarjan's algorithm; (2) a cycle-finding algorithm; and (3) a bidirectional search algorithm."

Finding Strong Components Using Depth-First Search Robert E. Tarjan, Uri Zwick https://arxiv.org/abs/2201.07197

matt_d··on Towards Unified Analysis of GPU Consistency [pdf]
Abstract:

"After more than 30 years of research, there is a solid understanding of the consistency guarantees given by CPU systems. Unfortunately, the same is not yet true for GPUs. The growing popularity of general purpose GPU programming has been a call for action which industry players like Nvidia and Khronos have answered by formalizing their Ptx and Vulkan consistency models. These models give precise answers to questions about program’s correctness. However, interpreting them still requires a level of expertise that escapes most developers, and the current tool support is insufficient.

To remedy this, we translated and integrated the Ptx and Vulkan models into the Dartagnan verification tool. This makes Dartagnan the first analysis tool for multiple GPU consistency models that can analyze real GPU code. During the validation of the translated models, we discovered two bugs in the original Ptx and Vulkan consistency models."

Dat3M: Memory Model Aware Verification https://github.com/hernanponcedeleon/Dat3M

matt_d··on Evolution of the ELF object file format
Removed, thanks!
matt_d··on Evolution of the ELF object file format
In case this is of interest, here's an attempt at gathering the references, including random blog posts (as well as articles, documentation, papers, software, and talks), on these topics:

- assembly & ISA (instruction set architecture):

- Arm: https://github.com/MattPD/cpplinks/blob/master/assembly.arm....

- RISC-V: https://github.com/MattPD/cpplinks/blob/master/assembly.risc...

- x86: https://github.com/MattPD/cpplinks/blob/master/assembly.x86....

- debugging: https://github.com/MattPD/cpplinks/blob/master/debugging.md

- debugging: tracing: https://github.com/MattPD/cpplinks/blob/master/debugging.tra...

- executable and object file formats (ELF, Mach-O, PE); debugging data formats (DWARF, PDB): https://github.com/MattPD/cpplinks/blob/master/executables.m...

- linking and loading: https://github.com/MattPD/cpplinks/blob/master/executables.l...

- compilers: https://github.com/MattPD/cpplinks/blob/master/compilers.md

- compilers correctness: https://github.com/MattPD/cpplinks/blob/master/compilers.cor...

matt_d··on What we learned from C++ atomics and memory model standardization [video]
The Future of Weak Memory (FOWM) 2024 talks: https://www.youtube.com/playlist?list=PLyrlk8Xaylp6u1S3R6gH0...

Abstract: https://popl24.sigplan.org/details/fowm-2024-papers/16/What-...

The C++11 memory model was first included with thread support in C++11, and then incrementally updated with later revisions. I plan to summarize what I learned, both as a C++ standards committee member, and more recently as a frequent user of this model, mentioning as many of these as I have time for:

The C++ committee began with a view that higher level synchronization facilities like mutexes and barriers should constitute perhaps 90% of thread synchronization, sequentially consistent atomics, maybe another 9%, and weakly ordered atomics the other 1%. What I’ve observed in C++ code is often very far from that. I see roughly as much atomics as mutex use, in spite of some official encouragement to the contrary. Much of that uses weakly ordered atomics. I see essentially no clever lock-free data structures, along the lines of lock-free linked lists in the code I work with. I do see a lot of atomic flags, counters, fixed-size caches implemented with atomics, and the like. Code bases vary, but I think this is not atypical.

In spite of their frequent use, the pay-off from weakly ordered atomics is decreasing, and is much less than it was in Pentium 4 times. The perceived benefit on most modern mainstream CPUs seems to significantly exceed the actual benefit, though probably not so on GPUs. In my mind this casts a bit of doubt on the need to expose dependency-based ordering, as in the unsuccessful memory_order_consume, to the programmer, in spite of an abundance of use cases. Even memory_order_seq_cst is often not significantly slower. I’ll illustrate with a microbenchmark.

We initially knew way too little about implementability on various architectures. This came back to bite us recently [Lahav et al.] This remains scary in places. Hardware constraints forced us into a change that makes the interaction between acquire/release and seq_cst hard to explain, and far less intuitive than I would like. It seems to be generally believed that this is hard or impossible to avoid with very high levels of concurrency, as with GPUs.

We knew at the start that the out-of-thin-air problem would be an issue. We initially tried to side-step it, which was a worse disaster than the current hand-waving. This has not stopped memory_order_relaxed from being widely used. Practical code seems to work, but it is not provably correct given the C++ spec, and I will argue that the line between this and non-working code will inherently remain too fuzzy for working programmers. [P1217]

Unsurprisingly, programmers very rarely read the memory model in the standard. We learned that commonly compiler writers do not either. The real audience for language memory models mostly consists of researchers who generate instruction mapping tables for particular architectures. The translation from a mathematical model to standardese is both error prone, and largely pointless. We need to find a way to avoid the standardese.

Atomics mappings are part of the platform application binary interface, and need to be standardized. They often include arbitrary conventions that need to be consistently followed by all compilers on a system for all programming languages. Later evolution of these conventions is not always practical. I’ll give a recent RISC-V example of such a problem.

matt_d··on Functional ownership through fractional uniqueness
I'd recommend by starting with the talk by Daniel Marshall (one of the authors) from Lambda Days 2023, "A Hitchhiker's Guide to Linearity", https://www.youtube.com/watch?v=QtlkqJGdnuM

The Granule Project's website, https://granule-project.github.io/, links relevant resources, too, in particular https://granule-project.github.io/granule.html and https://github.com/granule-project/granule/blob/main/example...

The latter tutorial is based on "Quantitative program reasoning with graded modal types" (ICFP 2019), with the talk and paper available at https://dl.acm.org/doi/10.1145/3341714

See also "Linearity and Uniqueness: An Entente Cordiale" (ESOP 2022), https://granule-project.github.io/papers/esop22-paper.pdf

matt_d··on Borrow Checking Hylo [video]
Paper: https://2023.splashcon.org/details/iwaco-2023-papers/5/Borro...

> Hylo is a language for high-level systems programming that promises safety without loss of efficiency. It is based on mutable value semantics, a discipline that emphasizes the independence of values to support local reasoning. The result—in contrast with approaches based on sophisticated aliasing restrictions—is an efficient, expressive language with a simple type system and no need for lifetime annotations.

> Safety guarantees in Hylo programs are verified by an abstract interpreter processing an intermediate representation, Hylo IR, that models lifetime properties with ghost instructions. Further, lifetime constraints are used to eliminate unnecessary memory allocations predictably.

https://www.hylo-lang.org/

https://github.com/Hylo-lang/Hylo

matt_d··on Representing Data Collections in an SSA Form [pdf]
Abstract:

"Compiler research and development has treated computation as the primary driver of performance improvements in C/C++ programs, leaving memory optimizations as a secondary consideration. Developers are currently handed the arduous task of describing both the semantics and layout of their data in memory, either manually or via libraries, prematurely lowering high-level data collections to a low-level view of memory for the compiler. Thus, the compiler can only glean conservative information about the memory in a program, e.g., alias analysis, and is further hampered by heavy memory optimizations. This paper proposes the Memory Object Intermediate Representation (MEMOIR), a language-agnostic SSA form for sequential and associative data collections, objects, and the fields contained therein. At the core of MEMOIR is a decoupling of the memory used to store data from that used to logically organize data. Through its SSA form, MEMOIR compilers can perform element-level analysis on data collections, enabling static analysis on the state of a collection or object at any given program point. To illustrate the power of this analysis, we perform dead element elimination, resulting in a 26.6% speedup on mcf from SPECINT 2017. With the degree of freedom to mutate memory layout, our MEMOIR compiler performs field elision and dead field elimination, reducing peak memory usage of mcf by 20.8%."

Programming Languages Amenable to MEMOIR

"At its core, MEMOIR proposes collections as value types. In this paper, we implement a library in C/C++ to provide this functionality, however many languages exist which provide the guarantees needed for a MEMOIR compiler. Languages with mutable value semantics [48], which degrades references to second-class citizens, are amenable to SSA construction, as they are analogous to our MUT library. Such languages include Swift’s struct types [69] and Hylo [70].

Languages with single-ownership, i.e., “borrowing”, which guarantee that only one mutable reference will exist at a time can be used to construct a MEMOIR program. An example of this is Rust [71], which is steadily entering the programming zeitgeist. Similarly to Rust, newer languages such as Mojo [72] and Vale [73] have similar ownership models. Of note, use ϕ ’s cannot be constructed for these languages, as multiple immutable references may exist at once. While the aforementioned languages are promising directions of future work, the lack of accepted benchmark suites implemented in them, unlike C/C++, was deemed too large a barrier to adoption in our research at present.

Collection-oriented languages [74–77] have existed for many years now. APL [74] and SETL [77] serve as prime examples of their philosophy, focusing on arrays and sets, respectively, as prime concepts of the language. As such they are interesting source languages for compilation and, furthermore, their implementations provide a wealth of resources on optimizing collection-oriented programs [78]. A recent example of these concepts being exploited outside of their original languages is parallel block-delayed sequences [79], which implements loop-fusion techniques on sequences as a library for Parallel ML and C++. Investigating the extent these optimizations could be performed statically with MEMOIR provides an interesting starting point for this line of research."

matt_d··on Databases in 2023: A Year in Review
Likely worth mentioning that Andy (the author) has been organizing an ML⇄DB Seminar Series (Machine Learning for Databases + Databases for Machine Learning) for the past few months (Fall 2023); materials & lectures: https://db.cs.cmu.edu/seminar2023/, https://www.youtube.com/playlist?list=PLSE8ODhjZXjYVdJKka5g3...
matt_d··on Tools for Learning LLVM TableGen
FWIW, its use has grown over time, with new applications most significantly including MLIR (Multi-Level IR compiler framework, which allows you to define your own intermediate representations as well as compiler passes operating on them), https://mlir.llvm.org/docs/DefiningDialects/Operations/

The docs have been improving, https://llvm.org/docs/TableGen/

I also like these resources:

Lessons in TableGen FOSDEM 2019; Nicolai Hähnle https://fosdem.org/2019/schedule/event/llvm_tablegen/

- What has TableGen ever done for us?, http://nhaehnle.blogspot.com/2018/02/tablegen-1-what-has-tab... - Functional Programming, http://nhaehnle.blogspot.com/2018/02/tablegen-2-functional-p... - Bits, http://nhaehnle.blogspot.com/2018/02/tablegen-3-bits.html - Resolving variables, http://nhaehnle.blogspot.com/2018/03/tablegen-4-resolving-va... - DAGs, http://nhaehnle.blogspot.com/2018/03/tablegen-5-dags.html

matt_d··on Multi-phase computation as an applicative functor [video]
Abstract:

> It is 50 years since Tony Hoare observed “certain close analogies between the methods used for structuring data and the methods for structuring a program which processes that data”. But programs have both static structure (following the data) and dynamic structure (execution), and these need not coincide. For example, breadth-first tree traversal should be executed across the grain of the tree structure. I will present a technique for resolving the tension between these conflicting forces: the static structure specifies a multi-phase computation, whose dynamic execution structure might be entirely different. The appropriate abstraction turns out to be an applicative functor - similar to but different from the free applicative.

> This is joint work with Oisin Kidney, Tom Schrijvers, and Nicolas Wu.

Related paper:

Phases in Software Architecture (architectural pearl) - The First ACM SIGPLAN Workshop on Functional Software Architecture - FP in the Large - http://www.cs.ox.ac.uk/jeremy.gibbons/publications/phases.pd... - https://icfp23.sigplan.org/details/funarch-2023/5/Phases-in-...

> The large-scale structure of executing a computation can often be thought of as being separated into distinct phases. But the most natural form in which to specify that computation may well have a different and conflicting structure. For example, the computation might consist of gathering data from some locations, processing it, then distributing the results back to the same locations; it may be executed in three phases—gather, process, distribute—but mostly conveniently specified orthogonally—by location. We have recently shown that this multi-phase structure can be expressed as a novel applicative functor (also known as an idiom, or lax monoidal functor). Here we summarize the idea from the perspective of software architecture. At the end, we speculate about applications to choreography and multi-tier architecture.

matt_d··on A History of Subtyping – Benjamin C. Pierce – PLMW @ ICFP 2023 [video]
Slides: https://www.cis.upenn.edu/~bcpierce/papers/2023-PLMW-Subtypi...
matt_d··on Arm’s Neoverse V2
The following is a pretty good overview:

"A Survey of Computer Architecture Simulation Techniques and Tools" - IEEE Access 2019 - Ayaz Akram, Lina Sawalha - https://ieeexplore.ieee.org/document/8718630

For more see also: https://github.com/MattPD/cpplinks/blob/master/comparch.md#e...

matt_d··on AST vs. Bytecode: Interpreters in the Age of Meta-Compilation [pdf]
Abstract:

> Thanks to partial evaluation and meta-tracing, it became practical to build language implementations that reach state-of-the-art peak performance by implementing only an interpreter. Systems such as RPython and the GraalVM provide components such as a garbage collector and just-in-time compiler in a language-agnostic manner, greatly reducing implementation effort. However, meta-compilation-based language implementations still need to improve further to reach the low memory use and fast warmup behavior that custom-built systems provide. A key element in this endeavor is interpreter performance. Folklore tells us that bytecode interpreters are superior to abstract-syntax-tree (AST) interpreters both in terms of memory use and run-time performance.

> This work assesses the trade-offs between AST and bytecode interpreters to verify common assumptions and whether they hold in the context of meta-compilation systems. We implemented four interpreters, an AST and a bytecode one, based on RPython as well as GraalVM. We keep the difference between the interpreters as small as feasible to be able to evaluate interpreter performance, peak performance, warmup, memory use, and the impact of individual optimizations.

> Our results show that both systems indeed reach performance close to Node.js/V8. Looking at interpreter-only performance, our AST interpreters are on par with, or even slightly faster than their bytecode counterparts. After just-in-time compilation, the results are roughly on par. This means bytecode interpreters do not have their widely assumed performance advantage. However, we can confirm that bytecodes are more compact in memory than ASTs, which becomes relevant for larger applications. However, for smaller applications, we noticed that bytecode interpreters allocate more memory because boxing avoidance is not as applicable, and because the bytecode interpreter structure requires memory, e.g., for a reified stack.

> Our results show AST interpreters to be competitive on top of meta-compilation systems. Together with possible engineering benefits, they should thus not be discounted so easily in favor of bytecode interpreters.

Artifact: https://zenodo.org/record/8198950

matt_d··on Tutorial: Teaching and Learning Compilers Incrementally
I know that SIGPLAN makes the regular talks from PLDI available at https://www.youtube.com/@acmsigplan although this doesn't always include tutorials (I can see there are some, but most are missing)
matt_d··on Tutorial: Teaching and Learning Compilers Incrementally
FWIW, https://pldi23.sigplan.org/details/pldi-2023-tutorials/8/Tea...

You should be able to work on the repository code (https://github.com/IUCompilerCourse/python-student-support-c... / https://github.com/IUCompilerCourse/public-student-support-c...) and test your implementation (although will need to rely on the books for guidance).

matt_d··on BinWrap: Hybrid Protection Against Native Node.js Add-Ons [pdf]
Abstract:

> Modern applications, written in high-level programming languages, enjoy the security benefits of memory and type safety. Unfortunately, even a single memory-unsafe library can wreak havoc on the rest of an otherwise safe application, nullifying all the security guarantees offered by the high-level language and its managed runtime. We perform a study across the Node.js ecosystem to understand the use patterns of binary add-ons (in Node.js applications).

> Taking the identified trends into account, we propose a new hybrid permission model aimed at protecting both a binary add-on and its language-specific wrapper. The permission model is applied all around a native add-on, and is enforced through a hybrid language-binary scheme that interposes on accesses to sensitive resources from all parts of the native library. We infer the add-on’s permission-set automatically, over both its binary and JavaScript sides, via a set of novel program analyses. Applied to a wide variety of native add-ons, we show that our framework, BinWrap, reduces access to sensitive resources, defends against real-world exploits, and imposes an overhead that ranges between 0.71%–10.40%.

matt_d··on Explaining my fast 6502 code generator
It could be fun to compare with Action!--it's been known to compile a reasonably good 6502 assembly (considerably better than other compiled languages for that platform), https://en.wikipedia.org/wiki/Action!_(programming_language),

It has been released as open-source together with the binaries, https://atariwiki.org/wiki/Wiki.jsp?page=Action

You should be able to run these using an Atari 8-bit (XL/XE model) emulator, like Atari800, https://github.com/atari800/atari800/releases or Altirra, https://www.virtualdub.org/altirra.html

matt_d··on Model Checking Futexes
PDF: https://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2023/SPI...
matt_d··on Language Design Meets Verifying Compilers (GPCE 2022 Keynote)
https://whileydave.com/publications/pea22_gpce/
← PreviousPage 2 of 5Next →