Posts

Wiki The Queueing Rule of Thumb (QROT) is an inequality that relates the number of servers, the number of service requestors, service time per requestor per server, and the maximum time to empty the queue as: num_server > (num_requestor * service_time) / max_drain_time Note: the servers are parallel. Most of this rule of thumb comes from algebraically moving around common metrics like arrival rate and service rate, but the core insight is in this invariant: arrival_rate / service_rate < num_servers. ...

My old boss used to tell me all the time that “you have to earn the right to do cool shit”. There are other, less cool, ways of saying the same thing - including: Fundamentals, fundamentals, fundamentals. Practice your scales, arpeggios, and etudes. Focus on the core parts of your business. Quantity has a quality of its own. This certainly isn’t a blanket statement, and it’s worth thinking about the nuances. ...

Last time, I was asking myself what the point of using RDTSCP was. Why shouldn’t I just call RDTSC and call it a day? How to Benchmark Code Execution Times (Intel Guide) explains the problem: When we call the RDTSC instruction, we pretend that the instruction will be executed exactly at the beginning and at the end of code being measured. The solution is to call a serializing instruction before calling the RDTSC one. A serializing instruction is an instruction that forces the CPU to complete every preceding instruction… before continuing the program execution. ...

TSC is a register that increments on every CPU tick. RDTSC is the assembly instruction that reads TSC into EDX:EAX. RDTSCP is the assembly instruction that reads TSC into EDX:EAX and also reads the processor ID (IA32_TSC_AUX) into ECX. Equivalent to doing RDTSC + RDPID in a single instruction. Benchmarking a critical session of code is probably as simple as start = rdtsc() // get current counter value .... beep boop, executing code .... cycles = rdtsc() - start // theoretically the number of cycles But things are, of course, a little more complicated. ...

An optimization of free() using boundary tags Last week, I was concerned about the performance of the coalescing algorithm. In particular - could I be smarter about coalescing by trading off memory for time? Memory is “cheap”, so I’m happy to store some extra bytes that facilitate the coalescing process. As a reminder, the two embedded data structures in the heap: struct FreeBlockHeader { size_t size; // size of free space FreeBlockHeader* next; // location of next free block }; struct AllocBlockHeader { size_t size; // size of allocated space }; The coalescing algorithm works by continuously comparing the head of the free list with every other node in the free list - until no more coalescing is possible. ...

In v0, we made the simplifying assumption that all the data we work with are fixed-size blocks. Now, we’re going to relax the assumption: data can now be requested in any size. Our simplifying assumptions meant that we didn’t have to track how much free space is available; we could just iterate over the blocks until we found one that was marked as empty. The problem with variable sizes is that now, we need to do some bookkeeping. When we request memory, our memory allocator needs to know: ...

For the next couple weeks, we’re going to write a memory allocator. I’m dumb, so I need to start from dead-simple problem constraints and work my way up to increasingly complex constraints. As such, we’ll write this allocator in stages. What is the memory allocation problem? Every process gets allocated memory - but some memory demands are more dynamic than others. This means that the programmer must bear responsibility over memory allocation. ...