Memory Mapped File IO

How often do you have to write a loop to read a file? Do you issue fscanf, fread, or perhaps create a stream via some object-oriented language?

Operating systems also provide support for easily reading in the entire file. A couple of function calls concluding with mmap() or MapViewOfFileEx() provides a char* pointer to the file's data. And with that, the file has been read into the program. So let's take a few moments to understand what the operating system is doing and use that to identify the advantages (and disadvantages) that memory mapping file IO provides.

When a program opens a file and performs IO via calls like fscanf, the program is using buffered IO. The operating system opens the file and sends IO operations based on the disk's granularity, which is at least 512B and often more. On a call like, fscanf(fp, "%d", &value), the program is requesting somewhere between 1 and 16 bytes, which is far less than the disk's block size. The operating system will read in the entire disk block and then copy the appropriate bytes to the program, while retaining the remained in its file cache. (By the way, the standard libraries also perform buffering, where the previous fscanf call might request 128 bytes from the OS and then process this data before returning to the application itself). Now, in making this call, how many copies of the data now exist in the system? There is one on disk, one in the OS's file cache, one in the standard library, and one in the application.

If the application requested the file via mmap, nothing happens except the OS reserves a range of the application's virtual address space for the file's data. Then when the application accesses an address in this range, the page fault will read in the data from the disk into the file cache and the virtual address will point to this same data.

If your program needs to make multiple passes through the file, or has a regular structure (such that a data structure could be defined, perhaps a future post on this), then memory mapped file IO can save time and space. However, if there are many small files, the file data only needs to be read once, or significant processing is required, then using a more "traditional" IO mechanism would be advisable.

Repost Are you a Programmer

Consider the question, what percentage of programs are released to the public (either commercial or open source)? Even excluding student assignments, this percentage may be far lower than one might think. My expectations are biased by having many friends at Apple, Facebook, Google, and Microsoft. But thinking further, I spent 10-20% of my time as a salaried employee doing just that, writing little programs. These coding projects were intended to help me do my job faster, which was contributing to a commercial software product.

This is my introduction to a piece of career advice regarding being a Computer Scientist (*cough* programmer), Don't Call Yourself a Programmer.

Repost Presentation Prep

So much of what I and many other Computer Scientists do is give presentations. When I worked full time, I prepared at least one presentation a month, often more, and wrote regular reports of my work for upper management. As a grad student, I give fewer, but still write many papers.

Not to say I'm anywhere near perfect at presenting, but I have come a long way in learning how to write and present, skills that I once thought had no relation to my profession. So let me again refer to another blog that outlines the time and steps required to prepare these presentations. Many people think they are ready to present with a just set of slides and skimp on these steps. I've sat through "dry runs" where the presenter hadn't even practiced. Or even presentations where the presenter isn't ready. So take the time and practice, otherwise we walk back to our desk and laugh about the latest speaker that we didn't understand.

Repost Heartbeat

I still do all the daily stuff. Read emails, commute to campus, research new ideas for conferences like POPL or PLDI, and imagine I'll someday have something that will squeak out to be posted. So when my usual routine leads me to another programming blog I read posting about POPL research etc, it seems I should copy them - Heartbeat. Blog is still alive.

Book Review: Masterminds of Programming

Several years ago I read a couple of interesting interviews with language designers, so my curiously was piqued by Masterminds of Programming: Conversations with the Creators of Major Programming Languages (Theory in Practice (O'Reilly)). While the title is pretentious, the premise was interesting in that here are 17 well-used languages, so what was the designer thinking? Why did he make the choices that he did?

Alas, it was not quite to be. Interesting yes, but the discussions were sometimes more general involving all of computer science. Yet nearly every interview had memorable lines and claims; a few of which I shall reproduce here:

"C is a reasonably good language for compilers to generate, but the idea that humans beings should program in it is completely absurd." - Bertrand Meyer, Eiffel

"One of our programming languages guys proposed a competition in which people would program the same program in all three of those [languages] and we'd see .... It turned out the only thing we figured out is it all depended on where the brightest programmer went...." - Charles Geschke, PostScript

"A good programmer writes good code quickly. Good code is correct, compact and readable. 'Quickly' means hours to days."
and
"An operating system does absolutely nothing for you. As long as you had something - a subroutine called a disk driver, a subroutine called some kind of communication support, in the modern world, it doesn't do anything else." - Chuck Moore, FORTH

"I do recommend [C++] and not everybody is reluctant. In fact, I don't see much reluctance in [system software or embedded systems] beyond the natural reluctance to try something new in established organizations. Rather, I see steady and significant growth in C++ use."
and
"I have never seen a program that could be written better in C than in C++. I don't think such a program could exist." - Bjarne Stroustrup, C++

So now I go to Amazon to remove the book from the list to read, and record a score of 3 out of 5.

Parallel Programming - Synchronization

Having submitted a paper this week to a conference, I have been lax on posting any updates.  With the submission behind me, I shall present another topic that has arisen recently in research and conversations - scalable synchronization.  For this post, I presume everyone has some knowledge of synchronization constructs like mutual exclusion, and knowledge of cache coherence is also valuable.  The story of this post begins 20 years ago when Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors was published.

This work studied the cost of mutexes / spinlocks and barriers.  They presented several different algorithms that scale well with increasing core counts.  When I read a work two decades old in Computer Science, at best I might think "Ah, here is where this idea was first proposed."  Which is true about the above work, but I also sit scratching my head and wondering how these ideas haven't diffused into common knowledge.

This post will focus on a single type of spinlock, the queued spinlock.  I'll discuss the hidden costs and dangers of common spinlocks and why it is sometimes worth using a queued spinlock.  Some of the authors were so good to propose several adaptations in Scalable queue-based spin locks with timeout, which I will also be discussing.  For this post, we will use an atomic_swap instruction, which is available (in one form or another) on modern architectures.

T atomic_swap(T* loc, T val){ T old = *loc; *loc = *val; return old;}

A basic (test-and-set) spinlock tries swapping in the value "locked" until it gets "unlocked" back, as follows.

void acquire_spinlock(int* lock)

{

    int value;

    do {

        value = atomic_swap(lock, LOCKED);

    } while (value == LOCKED);
}

Programmers soon realized that this implementation has some drawbacks.  Each core is constantly making requests for the same cache line and each one is trying to modify it.  The poor cache line is therefore going from processor to processor without anything useful happening.  So two changes were made: test-and-test-and-set and exponential backoff.  The following acquire routine has been extended with these changes, see "//".

void acquire_spinlock(int* lock)

{

    int value, delay = 1;

    value = atomic_swap(lock, LOCKED);

    while (value == LOCKED)

    {

        pause(delay); // take time before retrying

        delay = delay * 2;

        if (*lock != LOCKED) // test before swapping

            value = atomic_swap(lock, LOCKED);

    }

}

By delaying some time before attempting the lock again, each processor reduces its load on the memory system.  However, the core can be unlucky and be delaying when the lock is available, if it was released just after the test.  "Test-and-test-and-set" (TTS) is a simple paradigm where the code attempts an inexpensive check, like "*lock != LOCKED" before the expensive operation "atomic_swap".

However, TTS can still have many threads of execution enter the same expensive region.  The spinlock here is safe, but a programmer might have:

if (global_buffer == null) {global_buffer = malloc(SPACE);}

This sequence could have several threads attempting to allocate the same large buffer and therefore leaking memory, or worse.

But back to spinlocks.  With TTS, many threads have all requested read permissions for the lock's cache line.  Each sees that the lock is UNLOCKED and requests write permissions.  The cores are sending a storm of requests that will conclude with one core acquiring the lock and the rest spinning again.

Skipping over some intermediary research, the state of the art has generally settled on the queued spinlock.  The idea is that each waiter will spin on a local variable rather than the "lock" itself.  While both referenced works give code for the lock, it is relatively simple to derive once you know it exists (a fellow student and I worked out the algorithm in less than 30min), but I'll provide a sketch here.

struct entry

{

    volatile entry* next;

    volatile int state;

};

void acquire_queued_spinlock(void* lock, entry* me)

{

    me->next = null; 

    me->state = UNLOCKED;

    entry* prev = atomic_swap(lock, me);

    if (prev == null) return;  // lock is not held

    me->state = LOCKED;

    prev->next = me;

    while (me->state == LOCKED) ;

}

The queued spinlock only maintains a tail-pointer.  Each thread should have a pointer to its entry and insertions of new entries are only made to the tail.  After inserting, the thread has a unique pointer to the "old" tail of the queue, where it extends the queue.  The thread now spins on the local variable "me->state". Furthermore, on the release event, only one thread is unlocked, which minimizes the memory traffic from the cores fighting over the lock.  However, the queued lock is more expensive to acquire when there is no contention and it can be a greater pain to debug.

Reviewing the measurements in Algorithms..., the simple test-and-set spinlock performs best at very low levels of contention.  After a modest amount of lock contention, the TTS with exponential backoff is performing best.  But as the number of requests continue to increase, the queued spinlock dominates performance from then on.

As with all performance work, measure twice, cut once.  The correct spinlock for your parallel code will depend on: level of contention and the specific architecture of the system.

Performance is a Feature

Performance is a Feature discusses recent performance work for the site, stackoverflow.  I found the post interesting, albeit somewhat removed from my own work due to its web focus.  As always with performance, there are two things I highlight.  First, improve the biggest contributors first.  Second, after a certain threshold, further improvements may not matter.  For example, high frequency trading depends on the microseconds required, rendering a web page does not.