There are plenty of people enjoying designing, for example people who 3D print objects they design, or people designing PCBs or even entire gadgets but outsourcing production.

With LLMs, I guess a factor is how much direction you give the machine. “Build me a graphical desktop” likely isn’t very enjoyable, but I can see co-working with a LLM being enjoyable. Examples

- think of some novel UI interaction, and let the LLM code it

- spending hours to speed up the GUI or to make it use less memory

Knowing your limitations of building, but being good at designing and watching somebody/something else realise your vision is incredibly satisfying.

I see it like 3D printing. Nobody can extrude molten plastic out of their bodies to make things, but the skill of designing the construction well and then watch the machine execute it is certainly a good feeling. I dont really see how this is different to designing some software verbally and prompting an ai to build it for you.

Sure, that optimization interacts badly with the optimization that removes the infinite loop. But half the point of UB is to avoid needing to deal with such interactions, because they are defined out of existence.

Each number can be written in infinitely many ways, for example 12, 1.2E1, and 0.012E3 all are “twelve”

In (binary) IEEE floats, the canonical way to write floats is

  significant × 2^exponent

Float operations normally return numbers satisfying that.

However, in IEEE, the exponent cannot be made arbitrary small. Because of that, some very small numbers cannot be represented that way.

In those cases the standard says operations can return numbers with the value closest to the correct value with a significant less than 1. Those number representations are called subnormals.

If you use a CPU-local data structure, you must handle the case where, mid-way through a call to your allocator, the CPU runs a second thread that makes another call to your allocator (and that, too, can get interrupted by another thread that allocates memory, etc.)

That makes thread-local easier to implement and likely faster (it doesn’t require any memory barriers in the fast path)

Also, good schedulers try to avoid moving threads between CPUs. The better they manage to do that, the lower the cost of having per thread data structures (there likely still is a price, as there most of the time are more threads than CPUs on a system)

i don’t believe rseq based cpu local caches require memory barriers on the fast path.

  rseq_cs

   The rseq_cs field is a pointer to a struct rseq_cs. Is is NULL when no
   rseq assembly block critical section is active for the registered
   thread. Setting it to point to a critical section descriptor (struct
   rseq_cs) marks the beginning of the critical section.

No explicit memory barrier is required anywhere as the value is only read in supervisor mode and a privilege switch implicitly issues a LS-LS barrier on all major architectures. Even if you did not want to rely on that, you would only need a single S-LS barrier when you store the control structure the very first time.

Aha! So, to take advantage of that, a memory allocator uses the same abort handler for all operations?

If `rseq_cs` is no longer describing a relevant address, that is, the program counter has moved past it, the kernel just ignores it.

The code is executed by a single thread. Everything retires in program order. There is no need for a memory barrier between starting the critical section and its body.

Meanwhile the better the scheduler performs the more competitive the thread local approach becomes.

cost for interruption in an rseq critical section is that the PC gets overwritten to the rseq abort entry point before the task is rescheduled. no management thread necessary.

should be fairly minimal cost, especially assuming interruptions in the critical section are rare.

Giving it some more thought, I expect caches will typically be wiped out by a context switch. So the only place rseq is likely to benefit an allocator is on systems with multiple NUMA nodes where you'd like to make sure any management code isn't paying a penalty by hitting the wrong address range.

IIUC rseq (ie CPU local data) is primarily good for two things. The first being obviating the need for atomics (specifically the resultant cache line ping-pong) but thread local data already accomplishes that. The second being massive oversubscription of physical CPU cores (ie tens of thousands of threads) where TLS becomes utterly wasteful while also thrashing the cache.

maybe i give it too much weight, but:

> massive oversubscription of physical CPU cores (ie tens of thousands of threads) where TLS becomes utterly wasteful while also thrashing the cache

seems worth solving to me

If we do decide to concern ourselves with performance TLS has zero overhead and doesn't suffer from contention while rseq (at minimum) carries a penalty if preempted and involves setting a flag plus exhibits a data dependence for the address offset (the latter since AFAIK compilers don't natively support it as they do TLS). So while I'm certainly open to benchmarks to me it very much looks like a mixed bag that only comes up when you're already in questionable territory to begin with. In the event that we do step outside the norm I'd guess that a handful of threads with contention is a much more common scenario than thousands of threads per physical core exhibiting only minimal preemption.

I also expect something like a web server servicing thousands of requests in parallel to use an event loop instead of spawning an equivalent number of threads. I'm struggling to come up with a scenario where you haven't already fatally shot yourself in the foot and this remains a useful optimization to make. It's certainly relevant if you're using fibers (green threads, whatever you want to call them) but at that point you aren't in c calling malloc and your language runtime will (one hopes) already be taking care of all this for you.

Totally fair, and I agree that you should only have a few threads (or TPC) and shouldn’t be inundating the allocator with requests. But I’m only grinding this axe because I’ve personally had to deal with a system that went against most of that guidance.

We ran far too many threads in a memory-constrained environment. Thread count was many multiples of core count.

I totally agree that this is “questionable territory”, but honestly, any application that’s outgrown the basic glibc malloc has made a few mistakes.

That can be quite confusing. You had German mustache-man, Russian mustache-man, French mustache-man (Petain), French small-mustache-man (de Gaulle), Spanish small-moustache-man (Franco)

FTA: “When multiple threads simultaneously allocate or deallocate memory from the allocator, the allocator will serialize them. Programs making intensive use of the allocator actually slow down as the number of processors increases.”

The article does later retract on that, but that’s no reason to lead with such a blatantly false (with current allocators) statement.

Also FTA “In 2006, a third pool was introduced (after operating system memory pool and library-based memory pool) called the “arena”. Arena is a jemalloc-term”

Jemalloc is from around 2005 (http://jemalloc.net/), the idea of arenas is from the 1960s, and Wikipedia claims the term was coined in 1990 (https://en.wikipedia.org/wiki/Region-based_memory_management...), and the linked paper (https://www.cs.princeton.edu/techreports/1988/191.pdf) is from 1988.

Then, a typo: “as well as memory tied to specific to each of the multiple CPU core or even CPU infinity.”

“Infinity” should be “affinity” there.

> "The first memory allocation scheme started with a stack-based memory allocation. Next came the dynamic-based memory allocation scheme where linked-list and bucket-heap mechanism are used to divide the private-heap using size class approach. Soon, garbage collection algorithm introduced the initial backend of the memory allocation scheme."

Since no specific operating system is mentioned, these sentences appear to refer to the general history of dynamic memory allocation, in which case they are wrong.

"malloc" is a late comer in this history. It has appeared as the statement "ALLOCATE", together with the statement "FREE", in the programming language PL/I of IBM, by the end of 1964. The C programming language has inherited these 2 functions from IBM PL/I, together with several other features.

At that time (1964-12), many other techniques of managing memory had already been used for a few years.

Dynamic allocation of memory has started during the fifties, with allocation without ever freeing the allocated memory before the termination of the process.

Then, in 1960, 3 methods of handling dynamic memory allocation and implicit freeing were published, which have remained important until today: the use of garbage collectors in April (John McCarthy), the use of stacks in May (E. W. Dijkstra), and the use of reference counts in December (George E. Collins @ IBM).

So the use of garbage collectors is actually the oldest published method for handling dynamic memory allocation, not a newer method, being used in LISP I about 5 years before the first release of PL/I with explicit allocation and freeing (mid 1965).

Will research that, citations and all

Garbage collectors: "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", John McCarthy, Communications of the ACM, 1960-04, pp. 184-195 (open access at ACM).

Stacks and stack pointers: "Recursive Programming", Edsger Wybe Dijkstra, 1960-05-11 (available at the Dijkstra Archive).

Reference counts for memory allocation: "A Method for Overlapping and Erasure of Lists", George E. Collins (IBM), Communications of the ACM, Volume 3, Issue 12, 1960-12, pp. 655–657 (open access at ACM).

The first "malloc", i.e. the statements "ALLOCATE" and "FREE" appeared in "NPL Technical Report" at IBM in 1964-12 (available at bitsavers.org).

"NPL" was a provisional name for the new programming language of IBM, which was rebranded as "PL/I" when it was launched officially, a half of year later.

IBM did not document what kind of algorithm was used by their "malloc" implementation, but it already had to handle multi-threaded programs and it was specified that when a new thread was spawned, it could still access any variable that had been dynamically allocated in the parent thread, before the launching of the new thread, but the variables that were allocated in the new thread were private to that thread.

The C "malloc" became compatible with multi-threading only many decades after its ancestor from PL/I.

And then THeIR citations too!

Thank you very much!

I got tired of reading AI prose so I compiled and wrote it from my collections of others' whitepapers.

As a "For Reference Only", at the very least, for me.

As usual, anyone is welcome to improve upon it under CC BY-NC-SA.

allocators are so simple to just swap into your program. if you can put together a few representative workloads, you should just try out a few allocators and profile whatever metrics you care about.

https://news.ycombinator.com/item?id=47403847

I am intrigued.

Is there a source for them?

for us, tc was among the fastest in runtime while being very space efficient [0]. large rust application using far too many threads.

we’ve since also had great success with tc’s built in profiling tools.

[0]: https://news.ycombinator.com/item?id=47403847

We've tried tcmalloc, too. I don't remember the exact details, but we basically ended using jemalloc because it was using way less memory.

Same story with mimalloc - it usually provided a tiny bit more speed, but required more cpu and memory.

to confirm, you were using tcmalloc from https://github.com/google/tcmalloc and not from https://github.com/gperftools/gperftools, right?

the latter is a lot worse iiuc.

[0]: https://github.com/google/tcmalloc/blob/master/docs/gperftoo...

Compilations are hard to get 100% right.

What may cause issues is that they may not know the character class of the newly added code points. That can affect such things as

- upper casing or lower casing strings

- sorting of strings

- matching Unicode digits in regular expressions

There also can be bug fixes/improvements/tweaks that affect behavior. For example, in this release, https://www.unicode.org/versions/Unicode18.0.0/#UAX_Changes states

“UAX #14 Unicode Line Breaking Algorithm

Rule LB12a was changed to disallow a break between BA and GL. The Line_Break assignment of FIGURE DASH and EN DASH was changed from HH to BA and SOFT HYPHEN from BA to HH for better linebreaking behavior for those characters.”

⇒ if a language has functionality for detecting line breaking points, it must choose between backwards compatibility and following this change.

For example they iterate characters and test as characters and not code points, so that logic will be broken on codepoints.

> a tiny 4B model went from not being able to understand the harness it was wrapped in, to achieving a 1.81x geometric mean speedup and a summed latency decrease of 44.7% across a workload of join-heavy SQL queries

I can’t find it in the article (may have skimmed it too much), but I suspect they didn’t include those ~95 hours in the benchmark numbers.

I think all database vendors know their query optimizers could do much better if they could afford to spend lots of time to derive query plans.

⇒ this may be useful for some workloads, but even then, can you afford to spend hours every now and then to update your 4B model to ensure it still picks a good query plan?

I think this would be likely comparable to a scheduled backup, so I think it would be an acceptable maintenance window. However, deterministic algorithms would likely beat re-training (or re-fine-tuning) the model. For example, one could analyze actual distributions or whatever (instead of assuming uniform), and then some plans would automatically be eliminated.

Imo a good thought experiment is to look at places that are hyper-optimized, like compilers. Would LLMs bring anything to the table (architecturally or performance-wise) to a piece of software that has been carefully crafted for decades? (Methinks no.)

As an example, register allocation is graph colouring, and thus NP complete; a model for producing an allocation plan is learning heuristics that might look at more features in combination than the ones hand-crafted into the compiler. An LLM for the job might do better than a more focused model like a GNN, due to sheer size, the effectiveness of transformers, or magic. But it probably won't do an overall better job than the handcrafted heuristics, because those handcrafted heuristics also tend to compile very, very fast with a small memory footprint, and can be debugged (more) easily when they go wrong.

Postgres keeps histograms (including N most common values) for all columns; it does not blindly assume uniform distributions. (Presumably an LLM would have access to the same histograms.)

‘create plan llm_optimized …’

‘create view foo (select x, y, z from table bar) with plan llm_optimized’

> n! < exp(n log n)

Why would that be surprising? I can see that many wouldn’t know whether it’s true, but

  exp(n × log n) =
  exp(log(n) × n) =
  exp(log(n))^n =
  n^n

    1 × 2 × 3 × 4 × … × n
  < n × n × n × n × … × n