Search This Blog

Wednesday, May 24, 2006

Looks Like I Forgot to Mention Something

Hoard was actually fixed two or three days after I made the last post about it. The author updated it to support 64 KB block size, and it now completes my benchmark.

Speaking of which, I've managed to gather quite a bit of data with that thing; unfortunately, I don't have a program that works that is capable of graphing several million data points. Mathematica just falls over and dies when I try to open my data files, R bugs out when attempting to graph the data, and SciLab has the tendency to kill my computer. GnuPlot seems pretty nice, but doesn't support regression, for determining complexity. Though at least it can graph the points; I may have to take what I can get :P

Sunday, May 21, 2006

Okay, Enough of That

I see my blog's been hit by the spam bots. That means it's word verification time.

Saturday, May 20, 2006

**** Me!

So, I randomly decided to rerun MemTest 86 on my computer, following one of its many BSODs, of late. This proved rather... enlightening. The last time I'd ran it on my computer, it was showing one or two invalid bits every run (it was always only on test #7 - random data, which takes about 10 minutes). Today, however, it was finding bad bits at a rate of one every 10 seconds, or so... yeah, that's bad. At that point I wondered why on earth I'd kept using this CPU for so long, and immediately pulled it and replaced it with an old 1 Ghz Athlon, which is currently running MemTest 86 (and will be running some other diagnostics afterwards).

So, why did I (and still do) think that it's a problem with the L1 cache, as opposed to the memory, motherboard, or L2 cache (listed in order from most probable for a memory error)? After running MemTest 86 for several hours (it took that long when it was only generating errors every 10 minutes; now I can get as much info in only 10 or 15 minutes), I noticed that the errors were always at bit 27 of each 32-bit block of memory - the bit was 0 when it should have been 1. The addresses, however, varied widely, and spanned all three of my DIMMs. The probability of this being a memory problem was virtually 0.

However, while there was no relation among the upper bits in the addresses where failure appeared, the pattern in the lower bits was unmistakable: the lowest 16 bits were, without exception, 0x0194 or 0x8194. That is, the lowest 15 bits were identical in all cases.

Now, let's talk about my computer. It's an AMD Athlon XP 2200+. I looked up info on the AMD web site, and found that it had 128 KB of L1 cache, divided into 64 KB data and code caches. Both were 2-way set associative. The L2 cache consists of 256 KB of 16-way set associative cache. This information allowed me to make some predictions for what would happen if a bit was bad in both of them. 256 KB / 16 (-way set associative) would mean that a single bad bit would show up no more than every 16 KB. However, in the L1 cache, 64 KB (data cache) / 2 (-way set associative) means that a single bad bit would show up no more than every 32 KB - the exact pattern that was observed in MemTest 86, and even the same pattern observed in the BSOD crash dumps SW has been sorting through the last couple days.

Interestingly, as previously mentioned, only a single one of MemTest 86's tests showed a problem with the memory - the random number write/read test. All the rest of the tests use heuristics - methods that will detect failures common in memory chips due to the architecture of the chips. Thus it's not surprising that these tests would not be able to detect errors in the cache, with its entirely different architecture. Even still, I find it interesting to see this proven experimentally.


Update @ 6:24 PM: The new CPU has completed one full run of MemTest 86 (took about 1 3/4 hours) with no errors. While that's not a guarantee that it has no problems, it's almost certain that the bad bit problem in the previous CPU is gone, now.

Friday, May 19, 2006

Rootkit Ho?

So, my computer's been pretty unstable since I reinstalled Windows the last time, which was like 6 months ago. It BSODs like once every few days, on average, and on really bad days it may BSOD several times. So, I sicced (is that even a word?) SW on the problem. Windows is able to perform system dumps on BSOD, which allow someone (like SW) to examine the system at the point of BSOD at some later time.

Seems like he's off on lunch break at the moment, but before that he found that something is hooking the system call table (NtConnectPort, to be precise) and forwarding it to dynamically generated code. In kernel mode. So it's not real surprising that it crashes from time to time. That just leaves the question of WHAT is hooking the call, and WHY.

UPDATE @ 12:58 PM: It's Symantec Antivirus that's doing the rootkit-like behavior. It's not yet known whether that is what's causing the BSODs, though. We're gonna try a virtual sting operation to find out.

UPDATE: It appears to be due to a hardware failure. 1 bit is occasionally being 0 when it should be 1. I believe this to be the same problem I saw with MemTest 86 several months ago. If I recall correctly (I can't find the stuff I wrote down back them), the addresses memory errors occurred at always had the same lower 15 bits, and the upper portion of the addresses was essentially random. This led me to hypothesize that there is a bad bit in the L1 cache. I may need to code (or pirate) an L1 cache diagnostic program.

Thursday, May 18, 2006

The Rotary Set Implementation

The implementation is actually pretty straightforward. I've been trying to think of a way to implement such a thing in a completely lock-free manner for a couple days, and I haven't been able to come up with a solution. However, with the restriction of only a single writer, that makes things much easier.

The implementation is that of a circular doubly-linked list, but there are a couple tricks to making it work. First, readers only traverse the list in one direction: forward. That means that only the forward links and the head pointer need be kept valid at all times. In fact, I don't even declare the backward pointer in the nodes as volatile.

That brings us down to two variables that must be kept in sync: the forward links and the head pointer. However, with some careful instruction ordering, we find that we don't need to keep the head pointer coherent with the forward links 100% of the time (though the forward links must always be coherent).

The trick is to know where the linearization points are - the points where changes atomically take effect (atomic from the perspective of the readers). In the cases of both the insertion and deletion, this point occurs when we set the previous node's forward pointer to a new location (either the node we just allocated, in the former scenario, or the node after the one we're deleting). So long as this step is performed atomically, the change will be seamless to the readers. In the case of insertion, we have to set up the new node before doing this, of course. We have to, at the very minimum, set the new node's forward pointer to the node we're inserting before. Once that's done, we can link to the new node, and the chain will always be kept coherent in the forward direction.

That just leaves the matter of the head pointer. To save a bit of speed, new nodes are inserted right after the head node. That means we won't need to change the head pointer for insertions (unless the list was empty, in which case it's a trivial matter of setting the head pointer to the new node after we've made the node's links point to itself).

For deletions, however, there's always the chance that the head pointer will be pointing at the node we want to delete. But this is okay. It's okay for the head pointer to point to the node we're deleting, until we actually free the node's memory (and even then we use hazard pointers, in case some thread is still holding a pointer to it). In this case the linearization point just occurs slightly later: when the head pointer gets changed to point to the node after the deleted node. If a reader tries to read the node we’re deleting and then advances the head, it will just move the head to point to the node after the node we’re deleting, which we were going to do, anyway. At no time does a garbage pointer exist anywhere; thus it's fully thread-safe.

So, those are the solutions for the "hard parts". The rest is just vanilla hazard pointers, atomic compare/exchanges, and memory barriers.

Factoid

Was just talking to Merlin last night, and he told me something interesting: Windows isn't the ONLY OS that uses allocation granularity larger than a page size. IRIX (an SGI Unix, IIRC) does this, as well.

Wednesday, May 17, 2006

SWMR Rotary Set Ho!

Let me start off by explaining that SWMR is Single-Writer Multiple-Reader. That means that any number of threads may read from something, but only one thread may write to it, at any given time. In this particular case it's not quite as good as a totally lock-free structure - it's lock-free for readers, but the single writer status must be protected by a mutex (and the mutex does not prevent read access). In some cases (like this one) this is acceptable.

So, what in Kaity's name is a rotary set? Well, I basically made that name up (along with the structure, itself), with the intent of being as descriptive as possible. I don't know if anyone's conceived of this structure before, but I'd be surprised if nobody had. A rotary set is an unordered circular set. Yes, there's a good reason you'd want a circular set. As with normal list-based sets, there is a single head pointer (never mind the fact that it's not actually the head); however, this pointer doesn't always point to the same place. It's called a rotary set because this pointer can revolve around the set, one node at a time - it's as if the circular set is rotating.

Now, what use could such a thing possibly be? Well, I created it to solve a very specific problem. One of the projects on my todo list is to create an audio streaming system for games. As I want this system to take advantage of multiple CPUs wherever possible, that necessitates using an absolute minimum number of mutexes.

One of the central structures in the system is the list of playing streams for decoding. Let's have a little look at the requirements for this list. First, it has to keep track of all playing streams, like a set. However, making the most efficient use of the CPU (especially if you have multiple non-dedicated threads decoding) dictates that you process these streams in a round-robin fashion. You decode an appropriate amount of data on one stream, then move on to the next, stopping when you've used a large enough portion of the CPU (or run out of buffer space for decoded data). Oh, and these decoding threads will be running at maximal priority, to ensure the sound card doesn't ever run out of data to play.

Given these requirements, a little mental math will tell you that protecting such a list with a mutex would be a very bad idea. What if a thread trying to add a new stream to the list (or remove a stream from the list) runs out of CPU time while it's in the mutex? Why, you could have one (or more) high-priority (and in fact hardware-linked) threads blocking for some unspecified period of time. As I mentioned in a previous post, that's BAD.

The SWMR rotary set is my solution. It supports the following operations:
- Get head: gets the value of the head item. O(1). Lock-free.
- Pull head: gets the value of the head item, and moves the head pointer to the next node in the set. O(1). Lock-free.
- Insert: adds an entry to the set in an arbitrary position (decided by the implementation). O(1). Requires writer lock.
- Delete: deletes the specified entry (based on a key) from the set, regardless of where in the set it is. O(N). Requires writer lock.

Lastly, I should note that I haven't yet written the code for it, so I'm not 100% certain it will work. But I've managed to solve the three or four problems I've been able to find with the concept (and don't know of any others, at the moment).

AAAAAHHHHHHHHHH

So, I finally got Hoard to compile. Now I just need to change the allocation unit size from 8 KB to 64 KB. Easy, right? BZZZZZZZZZZZZT

For those of you familiar with Crypto++, this thing's source is about that bad. There are like 70 header files, and more template use than one person could possibly learn. But I managed to find the places I needed to change to make it use larger block size. Unfortunately, this guy has hard-coded literally more than 2,000 constants (parameters) for different block sizes - 4 KB, 8 KB, and 16 KB. I guess that explains why he hasn't fixed the problem I reported - it'd take even him a few days to add a completely new block size, and he wrote the thing.

I'm officially giving up on fixing this thing myself :P

Monday, May 15, 2006

Here We Go, Again

So, it's finals time. One final, in particular, sounds extremely amusing. Of course I'm speaking in my typical sarcastic tone. I seem to recall ranting about how bad one round of tests earlier this semester was; it's the same class as one of those I said was too long. But this time, things are a little different: three essay questions instead of two, and six short-answer questions instead of five (I think it was five; maybe it was four). That's right, it's 25-30% longer than the last one, in the same amount of time. And this guy wonders why no one in his class has EVER gotten an A on the final (he said that at one point in the class) - no one has ever FINISHED the final. Or maybe it's not a surprise to him at all, and simply that he doesn't WANT anyone to ever get an A on his final.

Sunday, May 14, 2006

For the Curious

Why DOES Windows have gay 64 KB allocation granularity, anyway? Raymond explains that it's a vestige of an old Alpha processor that Windows (NT) used to run on.

Saturday, May 13, 2006

Errata

It looks like I was mistaken about something. It's indeed true that reservations must begin on a multiple of 64 KB. I assumed this also meant that they also had to end on a 64 KB boundary. From Programming Applications for Windows (what I just looked it up in):

Whenever you reserve a region of address space, the system ensures that the region begins on an allocation granularity boundary. The allocation granularity can vary from one CPU platform to another. However, as of this writing, all the CPU platforms (x86, 32-bit Alpha, 64-bit Alpha, and IA-64) use the same allocation granularity of 64 KB.

When you reserve a region of address space, the system ensures that the size of the region is a multiple of the system's page size. A page is a unit of memory that the system uses in managing memory. Like the allocation granularity, the page size can vary from one CPU to another. The x86 uses a 4-KB page size, whereas the Alpha (when running both 32-bit Windows 2000 and 64-bit Windows 2000) uses an 8-KB page size. At the time of this writing, Microsoft expects the IA-64 to also use an 8-KB page size. However, Microsoft might switch to a larger page size (16 KB or higher) if testing indicates better overall system performance.

So it seems the mystery of the 8 KB reserved region wasn't really a mystery at all.

As for Hoard, after I reported the issue on the mailing list, the author acknowledged the existence of the flaw earlier today. At the time I was doing the debugging, I guessed (and I still believe) that he's a Unix guy, and so wasn't aware of the quirky way Windows handles allocating memory (that is, the 64 KB allocation granularity). Hopefully he'll fix it pretty soon, because Gord knows I'm too lazy to do it :P

Allocator Benchmark WTF

So, I've been working on this allocator benchmark for the last few days. Essentially, the program has been completely redone. It now uses profile data gathered from some real application by helper programs. Right now I'm using the data from a couple games of Warcraft 3. Now it also logs frees and reallocations, as well as allocations.

Hoard, however, is exactly the same as it was in the previous version: not working. It starts failing allocations with about 350 megs allocated, for reasons that can only be described as Outer Limitsish. At 350 megs, my virtual address space is nowhere near full, nor is my physical memory or virtual memory. Yet the author of Hoard swears that Hoard will not fail unless it runs out of memory. The answer turned out to be the weirdest of both worlds.

This is what WinDbg (may I just say that I loathe that stupid program) has to say about the memory state of the program, at the point of the crash (due to new returning NULL and it getting accessed):

-------------------- State SUMMARY --------------------------
TotSize ( KB) Pct(Tots) Usage
16507000 ( 365596) : 17.43% : MEM_COMMIT
69470000 ( 1724864) : 82.25% : MEM_FREE
679000 ( 6628) : 00.32% : MEM_RESERVE

Largest free region: Base 00000000 - Size 00010000 (64 KB)
Okay, so the quantities of committed, free, and reserved memory are about what you'd expect (actually, I would have expected reserved memory would have been a lot higher, but that's relatively unimportant). The real WTF is that last line. When I first saw that, I thought it had to be BS. With 372,224 KB allocated/reserved, the worst-case scenario would be that an equal amount of memory would be diced into 64 KB blocks (this would be one 64 KB allocation unit being committed/reserved, the next free, etc.). That would leave about 65% of the address space completely free, and the largest free block size should be a few orders of magnitude larger than 64 KB.

Nevertheless, here's what WinDbg has to say about the virtual address space (a little fragment of it):

68362000 : 68362000 - 0000e000
Type 00000000
Protect 00000001 PAGE_NOACCESS
State 00010000 MEM_FREE
Usage RegionUsageFree
68372000 : 68372000 - 0000e000
Type 00000000
Protect 00000001 PAGE_NOACCESS
State 00010000 MEM_FREE
Usage RegionUsageFree
68382000 : 68382000 - 0000e000
Type 00000000
Protect 00000001 PAGE_NOACCESS
State 00010000 MEM_FREE
Usage RegionUsageFree
68392000 : 68392000 - 0000e000
Type 00000000
Protect 00000001 PAGE_NOACCESS
State 00010000 MEM_FREE
Usage RegionUsageFree
683a2000 : 683a2000 - 0000e000
Type 00000000
Protect 00000001 PAGE_NOACCESS
State 00010000 MEM_FREE
Usage RegionUsageFree
683b2000 : 683b2000 - 0000e000
Type 00000000
Protect 00000001 PAGE_NOACCESS
State 00010000 MEM_FREE
Usage RegionUsageFree
683c2000 : 683c2000 - 0000e000
Type 00000000
Protect 00000001 PAGE_NOACCESS
State 00010000 MEM_FREE
Usage RegionUsageFree

And on it goes, for hundreds of pages. This is just mind-boggling: all these blocks of free space smaller than 64 KB. Querying WinDbg confirms what seems probable from this list: in between each of those blocks are a couple pages of allocated memory.

For those not familiar with Windows memory allocation, there are two levels of allocation: reserve and commit. Reserve reserves a region of the address space, preventing it from being used to allocate memory unless you explicitly tell Windows to allocate from that region. Commit allocates actual memory to the region - either physical memory, or space in the page file. This allows you to, for example, reserve a huge contiguous block of memory for a buffer, but only allocate it as you actually need the memory (e.g. realloc).

Now, reserving is done by the allocation unit, which is usually 64 KB. This means that you must reserve starting at a 64 KB boundary, and reserve some size that is a multiple of 64 KB. Committing is done by the page size - usually 4 KB (note that you can only commit memory out of a reserved region, although you can do both in one system call). That means you can have a 64 KB block that is partially committed and partially reserved. I know of no way to have 8 KB of a 64 KB block committed, and the other 56 KB not reserved (at least not from user mode), and I have absolutely no idea how Hoard has managed to accomplish this. But at least I know what the problem is, so I can get them to fix it.

Tuesday, May 09, 2006

Rebuttal

So, I sent a link to the benchmark to my friend in Blizzard. Surprisingly, it provoked a rather lengthy rebuttal from the "lead of our technology team" (who my friend forwarded my report to). I'm not sure if I'm allowed to post the original e-mail, so I'll just respond to the points in it.

It's true that it's an artificial benchmark. I was looking for a simple and elegant method that would have some resemblance to real-world data. I actually did consider writing a program to record every block of memory something like Warcraft 3 allocates, and then use that as input for my tests. But ultimately laziness got the better of me. Maybe sometime I'll try that.

I honestly hadn't considered the possibility that a memory allocator would be optimized for free time, rather than allocation time, as I expected free to take an almost negligible amount of time (this was why I only benchmarked allocations, because I expected that would be the bottleneck). I might have to do some free benchmarks as well, then.

I'm not quite certain what he meant by SMem being intended for use with multiple heaps (I can think of two possible meanings). I'm aware that SMem also supports the creation of private heaps, although I hadn't seen that used a great deal in my reverse-engineering (though my work is getting pretty dated; I'm not aware what techniques they used currently). If he's referring to slab allocation, that's great; that's the way to optimize allocation performance (which is why I added it to LibQ). This would, of course, produce drastically different results than the benchmark did; of course, it would also produce different results for HeapAlloc and Hoard (at least, if Hoard can do multiple heaps).

The other possibility is that he's referring to the global Storm heaps. For global allocations, Storm uses a set of 256 different heaps, each protected by a separate mutex. Which heap is used is based on the hash of a tag string for each allocation (typically this is either __FILE__ or the decorated name of the structure being allocated). I hadn't really thought that this was to promote similarity of data in each heap; I was thinking it was more to ensure that any two threads would virtually never lock the same heap at once. But if that's the case, it is conceivable that that could influence the results, as there might not be an even distribution of sizes, given the huge number of heaps.

The average block size was 256 bytes. The allocations were randomly chosen from 1 to 512 bytes, with equal probability. While equal probability may not be realistic, it might have been a good thing, given that I couldn't have imagined the bizarre shape of the SMemAlloc "curve" on the graph :P The reason for using numbers this small was based on the assumption that larger allocations would be fairly infrequent, so not as important, performance-wise (and very large blocks getting allocated from the OS). I was actually worried that I might skew the data in unrealistic ways if I made the maximum size any larger.

This was exclusively a single-threaded benchmark by design. There were two reasons for this, one being obvious: I don't have a multiprocessor system :P The other was that multiprocessor benchmarks are fairly common (i.e. on the Hoard site), and so didn't really justify a benchmark (remember that finding problems with Storm wasn't the original goal of the benchmark). That and the fact that multithreaded performance is relatively predictable: Vanilla HeapAlloc is going to do terribly (due to having a single heap mutex), Storm is going to be very fast (due to more or less never having allocation collisions). In fact, the allocator I'm working on is highly scalable (completely lock-free, and actually somewhat resembles the Windows low-fragmentation heap), but I also expected it to be faster than typical allocators for individual allocations (hence the survey of the competition).

Lastly, speaking of the Y axis of the graph, you might find this graph interesting, in which I uncapped the Y axis (I had manually capped it to give the best view of the data) :P

Allocator Benchmark

The graph I made from the benchmarks is here. Each point represents the average of all allocations of that size.

The test consisted of 7.5 million memory allocations (actually, Hoard only did 2.25 allocations, as that's all I could get it to do before crashing), of sizes ranging from 1 byte to 512 bytes; the total allocation size was generally around 400 MB (although this is a bit misleading, as explained later). A size was chosen randomly from that range, using a PRNG with a constant seed (to ensure reproducibility), and allocated with the corresponding function, each call benchmarked with the Pentium cycle counter instructions. Allocations were grouped into batches of 250, which were executed in real-time priority class (in other words, no thread time-slicing), with the thread sleeping after each batch (to prevent starvation of other threads). For the special case of SMemAlloc, the tag string of "BlubberyKaity" (an inside joke) was used, which I thought was a realistic length for the hashing function to chew on.

Approximately every 256 allocations, a purge was performed. Purges consisted of the freeing of 40% (this exact number is higher than I originally intended to use; it was used to prevent running out of physical memory on the test computer, while keeping the number of allocations the same) of the currently allocated blocks, chosen randomly. This was done as a crude attempt to simulate how memory freeing is often done in batches, after the completion of some task that required memory allocations.

At the moment the final memory allocated numbers are misleading, as they are the virtual memory space used at the end of the program run. This would naturally include the memory allocated for the trees used to hold the list of memory allocations (for frees and statistic gathering), and I would imagine they'd take up at least half that number.

HeapAlloc demonstrates a roughly O(log N) curve (where N is the allocation size). HeapAlloc, when using the low-fragmentation heap option, displays approximately O(1) complexity. The Hoard curve has a rather peculiar shape, and it's difficult to characterize it before around N = 280, where it seems to adopt a O(log N) shape. By far the strangest is SMemAlloc. From approximately N = 40 to 240, it seems to have a roughly O(1) shape, with a notable amount of inconsistency, despite very clear clustering. It appears that, for N = 0 to 40 and N = 240+, I takes on a O(x^N) shape (this is definitely true for the latter case, although the former range is fairly small to draw conclusions from).

It's also noteworthy to point out that Hoard worked a bit differently than the other allocators. Save for Hoard, all of them operated on private heaps (heaps that didn't have the allocation tracking stuff allocated from them). In the case of Hoard, I was only able to get it to work by letting it hook malloc and new (what it does by default). Consequently, all allocations, even ones not part of the test, were performed using Hoard. I don't know whether this may have biased the results, or in which direction.

Monday, May 08, 2006

Wooooow

So, I decided I'd do some memory allocation benchmarks before I worked on the lock-free, zero-fragmentation allocator I mentioned. I'll probably post more detailed information later, but for now here are a few key findings (either important or just interesting):
- When there is nothing but allocations, HeapAlloc/malloc/new appear to be O(log N) with respect to block size
- When there is a significant amount of deletions intermixed with allocations, HeapAlloc/malloc/new are O(1), and actually as fast or faster than HeapAlloc/malloc/new with allocations only (big surprise)
- HeapAlloc from a private heap is O(log N), faster than HeapAlloc from the global heap for allocations <> 100 bytes (also a big surprise).
- SMemAlloc is just about the biggest POS ever coded. By about 50 byte allocations it passes HeapAlloc/malloc/new, and continues in what appears to be O(N) (it's really hard to tell, because the data is all over the freakin' place; it could also be O(log N)). At 320 bytes, it becomes O(x^N), getting up to around 100 K cycles for 500 byte allocations. I know that's my shock and awe for the day.

Saturday, May 06, 2006

To Skew or Not To Skew - Part 2

It looks like my analysis of this lock-free priority queue was right on the money: the algorithm can be quite inefficient (about half as fast as the priority queue using a spin-lock). It seems that Herlihy (the guy who wrote the algorithm) did a fair bit of research on it back in 1993. He also managed to identify a solution to the problem: exponential back off.

While the article doesn't do benchmarks on the skew heap with exponential back off, the normal heap with exponential back off shows a remarkable increase in speed, performing superior to the spin lock version beginning at about 6 threads executing concurrently. At 16 processes contending for the same priority queue, the lock-free heap with exponential back off is about twice as fast as the spin lock version.

However, using exponential back off with the spinlock gets faster, still. The heap using a spinlock with exponential back off is about 65% faster than the lock-free heap with exponential back off.

Last, it should be noted that there's an inherent bias in these results. They all use artificial situations where memory access is minimized in the case of the spin lock version, so most of the access can be done from cache, in contrast to the lock-free algorithm. So it's possible that in real world scenarios the lock-free version will be faster, relative to the spin-lock version.

So, we got some nice information, but it really doesn't answer the question of whether I should implement this sucker :P

Friday, May 05, 2006

Goin' for the Gold!

So, that brings us to the third and final item on the list of lock-free thingamajiggers I wanted to add to LibQ (excluding the allocator; that thing is tricky to implement; I'll get around to that at some point): the atomic deque. And I've got a serious problem.

The algorithm requires the use of atomic memory writes larger than one word. This is something which, of the architectures I want LibQ to support, only x86-32 supports, making it highly impractical.

There are two ways to get around this. If you remember, I have this little thing called CAtomicVar, which allows atomic operations on types larger than one word, for a price: one memory allocation each time the variable is written to (typically this will be twice per push/pop, although in periods of high contention it may be more than that). A third allocation will be required for push operations.

That's pretty bad. Even with a free list allocator I'd wager that's at least 100 cycles inside the window of invalidation vulnerability, considerably more without a free list.

The other solution is to make the deque fixed size - it can only hold so many items, maximum. That's not all; this method will only work on CPUs that can atomically access 64-bit values. This is only supported on x86 and PPC64 (G5, I think) CPUs, leaving most Mac users out.

So, that's the problem, and those are the solutions. This brings up the question: is it worth it? If so, which method is better?

To Skew or Not To Skew

Two dilemmas in one day; how about that? This one is about this algorithm for a lock-free skew heap. Figuring out how this thing works just from the pseudo-code was a bit tricky, but I think I've got it, now. It works by reallocating every node it modifies in the skew merge, creating a partial duplicate in memory (recycling nodes where possible), then finally atomically activating the new tree by swapping out the root node.

So, that means about O(log N) allocations per enqueue/dequeue operation. This thing keeps its own free list of nodes, so allocations are relatively fast. Though I'm still a little worried. I can't imagine this thing taking less than a few hundred cycles to perform an operation (when there are 10 or 20 nodes), and if another thread modifies the tree while the operation is in progress, the entire operation gets discarded, and it tries again. That's an awfully hefty penalty for failure.

I'm not sure if it'd be better to write the thing and let it gobble up cycles when there's contention, or just leave you to use a mutex with a non-lock-free priority queue. With the other lock-free structures thus far, most of the time (allocating memory, etc.) can be done without any chance of it going to waste, as the window for another thread invalidating your work is very small (only a couple dozen cycles, and only the work done in that window will get invalidated if another thread gets there first). Here, the window is quite large; there's only so much you can do outside the window ahead of time (like maybe allocate plenty of memory to the free list so that you can be sure the list will be large enough to get you through the window; but even if you did you'd probably still have a window of a couple hundred cycles).

Put in more of layman’s terms, there isn't as much to gain from a lock-free priority queue as there is for the other lock-free structures.

To Wait or Not To Wait

So, I've been looking over these atomic structure algorithms (the ones I didn't implement already) again, now that I've got some relatively free time. I'm really having a hard time deciding whether to implement the wait-free variable.

The wait-free variable does exactly what the atomic variable does, only better: allow load/store with reserve, exchange, unconditional set, etc. The problem is that, like all the other atomic structures, the atomic variable is implemented with compare/exchange loops. This means that if there are a large number of threads setting that variable within a short period of time, a thread may have to spin for a while before it gets its turn to read the variable (one spin per thread that writes to the variable).

The wait-free variable partially circumvents this, allowing reads to be performed in constant time, regardless of how many other threads are trying to write to the variable. Writes, however, must still use compare/exchange loops (no way around that).

So, is it worth doing, or not?

Thursday, May 04, 2006

Very Squishy

I mentioned a few weeks ago that I had an algorithm for a lock-free memory allocator. I actually didn't look much at the algorithm for it until today, but it's pretty straightforward; allow me to make you drool a bit.

As mentioned previously, it's lock free. As with all lock free structures, that means that wasted cycles due to competition for it will be very low, even when many threads are trying to use it at once.

But the big deal is that it's zero fragmentation. Fragmentation is what happens when a small block gets freed, when there is still data allocated on both sides of the block. The block can now be reused, but only for requests for blocks the same size or smaller. This can have two bad effects. First, it can wear down your memory over time, by progressively creating smaller and smaller holes. At some point these holes cease to be useful, and they wind up being unusable allocated space. Second, it means that you have to keep a sorted list of free blocks, and go searching through it every time you need a block, to see if you can find one large enough; this makes allocations O(N) with respect to the number of free blocks.

Having a no fragmentation heap means that you can kiss both problems goodbye. You can run this thing for all eternity and you won't have any fragmentation. It's possible (if not probable) that some memory will still go unused, but that's simply because demand for blocks of a given size varies; if demand really high at one point, a bunch of memory will be allocated, and when demand drops, some of that memory will go unused. This isn't the same thing as fragmentation; the memory is still just as useful as the first time it was allocated, it just isn't being used.

Not only that, but I've got three words for you: constant time allocation. No matter how much you use this thing, it'll always be just as fast to allocate memory. Even better, this constant time is very low; likely significantly faster than a single call to malloc (the default implementation, anyway). It doesn't get much better than this.

However, there's a caveat. The simplest and surest way of implementing a zero-fragmentation allocator (and indeed what this one uses) is with a simple trick: you have separate heaps for memory of different sizes, and round allocations up, so that all blocks in a single heap are of the same size. This makes it inherently wasteful (at least when the blocks getting allocated aren't exactly the size of each block of the heap). The amount of waste may be tweaked by how you slice up your heaps. I'll have to do some playing around with this. Here's what I'm thinking at the moment for heap block sizes (note that I haven't spent much time thinking about this yet; I'm basically coming up with these numbers as I type):
- one heap for each power of two and 1.5x each power of two from 32 bytes to 8 KB
- one heap for 1, 1.25, 1.5, 1.75x each power of two from 8 KB to 64 KB
- anything larger than 64 KB gets allocated directly by the OS (VirtualAlloc, etc.)

More or less that means that for blocks 32 bytes to 8 KB, no more than 1/2 of the requested size will be wasted. For blocks 8-64 KB no more than 1/4 of the requested size will be wasted.

Increasing the number of heaps would serve to reduce the waste, but be aware that all allocations will have to locate the correct heap. That means it will do a binary search on the table of heaps, which takes O(log N) time. Also, increasing the number of heaps wastes memory in another way: all memory must eventually be allocated from the OS in large (probably 64 KB) blocks. Each heap that has at least 1 item allocated at some point will have one of these blocks associated with it. If you have a 64 KB block of memory that only has a single 32 byte allocation, that's a rather catastrophic (percentage-wise, anyway) waste of memory. On the other hand, if you're writing something like World of Warcraft, which allocates hundreds of megs of memory of widely varying sizes, a few megs of wasted space for unused blocks (1 megs would be 16 heaps) is probably worth it. So, I'll probably allow you to tweak the heap organization for your own projects as needed.

Wow, that post turned out to be way longer than I expected. Story of my life, I guess...

Tuesday, May 02, 2006

& More Good Anime

Some new animes worth watching, if you do that kind of thing. School Rumble, one of my old favorites, is now in season 2. Also currently airing is The Melancholy of Haruhi Suzumiya, about possibly the most insane girl you'll ever see (even by anime standards). Also, the infamous Squid has sent me Strawberry Marshmallow, which I'm currently watching. Not a bad series, although it may be for a bit younger audiences.

Monday, May 01, 2006

& Public Service Announcements

Fact: good looking (by any normal standard) girls that are math majors do exist. Now if you'll excuse me, I'm going to go try and rectify the situation before the universe collapses in on itself.

*loads shotguns*

Saturday, April 29, 2006

Updated

I updated the atomic structures module so that all the structures now support allocators through CStaticAllocator (basically a simpler version of allocator, which was needed for technical reasons). This isn't so useful in and of itself, but now that allocator support is in I can add the free list allocator, which could be a significant improvement, depending on how you use the structures. Also, some structures do more allocating and freeing in general, and so really need a free list allocator to keep the speed up (the atomic and wait-free variables, and skew heap priority queue come readily to mind).

Also, I uploaded Base.cpp; nothing in it other than a couple of static variable instantiations, but you'll need it to compile LibQ, and I forgot to upload it before :P

Thursday, April 27, 2006

& Wii

I usually don't cover stuff like this, but this was just so shocking I had to post it. The official name for the Nintendo Revolution has been announced: Wii. See, the Japanese have this thing called seppuku; somebody needs to use it.

& Immunology Fun

So, tomorrow we have our papers for immunology class due; basically the papers are a summary of some line of research, which is semi-extra credit. We were paired off so that another student could give their feedback on our first drafts before turning in the final version. I found a pretty cool piece of research, and it seems I wasn't the only one. The abstract of the paper I found:
Lupus, a multigenic autoimmune condition in which a breakdown of tolerance results in the development of autoantibodies, leads to a variety of pathologic outcomes. Despite the heterogeneity of factors influencing disease susceptibility, we demonstrate that the partial restoration of inhibitory Fc receptor (FcgRIIB) levels on B cells in lupus-prone mouse strains is sufficient to restore tolerance and prevent autoimmunity. FcgRIIB regulates a common B cell checkpoint in genetically diverse lupus-prone mouse strains, and modest changes in its expression can result in either tolerance or autoimmunity. Therefore, increasing Fc{gamma}RIIB levels on B cells may be an effective way to treat autoimmune diseases.
What that means is that they managed to cure a class of autoimmune diseases by simply increasing expression of one receptor on B cells (antibody producing cells, basically). How cool is that?

The abstract of the article the person I'm paired with found:
Non-obese diabetic (NOD) mice develop spontaneous T-cell responses against pancreatic beta cells, leading to islet cell destruction and diabetes. Despite high genetic similarity, non-obese resistant (NOR) mice do not develop diabetes. We show here that spleen cells of both NOD and NOR mice respond to the islet cell antigen glutamic acid decarboxylase-65 in IFN-gamma-ELISPOT assays. Moreover, NOR-T cells induce periinsulitis in NOD SCID recipient mice. Thus, a potentially pathogenic islet cell-specific T-cell response arises in NOR and NOD mice alike; the mechanism that prevents the autoimmune progression of self-reactive T cells in NOR mice presumably acts at the level of effector function. Consistent with this hypothesis, CD4+CD25+ cell-depleted spleen cells from NOR mice mediated islet cell destruction and overt diabetes in NOD SCID mice. Therefore, islet cell-specific effector cells in NOR mice appear to be under the control of CD4+CD25+ regulatory T cells, confirming the importance of regulatory cells in the control of autoimmune diabetes.
What that means: there are two strains of mice, one (NOD) which is prone to diabetes, the other (NOR) not, yet the two strains are extremely similar to each other genetically. In both strains the immune system builds up in preparation to attack insulin-producing cells in the pancreas (the cause of this type of diabetes), but in only one of the strains (NOD) does it actually attack. The exact reason for this is unknown, but it seems to have something to do with one type of immune cell (CD4+, CD25+ T cells).

I thought this one line from the article was humorous: "...would permit to address this hypothesis." Can't find a pronoun that fits? Just omit it completely!

Lastly, note that these papers can be thought of as press-releases. The authors may claim things that are/could be wrong. For example, in the first article they used four different strains of mice in the experiment, which consisted of collecting data a good dozen ways. However, not all of the data is shown for all four strains; some data they only show data for one strain. I wonder why.

Sunday, April 16, 2006

3, 2, 1, Contact!

And LibQ is live. Some of it, anyway. Right now just the atomic primitives and structures, as well as a few misc. helper classes. As of right now none of LibQ has been tested on non-Wintel. It's up on Subversion (anonymous read access only) running on BZ's server, as well as being accessable through Trac. Oh yeah, and I still haven't managed to get Merlin to proof-read the atomic stuff and help me figure out where memory barriers need to go.

Saturday, April 15, 2006

Today's Status

Okay, I've got atomic stack, queue, O(N) set, O(N) hash table (constant time when the number of items is less than the size of the hash table). Also have an atomic variable template that supports atomic get/set (even on structures or variables larger than 1 word) and load/store with reserve, and is fully immune to the ABA problem; however, it's significantly slower (like, an order of magnitude) than a simple AtomicCompareExchange, so if it's possible to use that, you should. But if you need immunity to the ABA problem, or need to atomically access a variable larger than 1 word, you don't have much choice.

Flunked!

Intuit's ItsDeductable 2005 (comes with TurboTax) has just become the first program to receive a Q Limited User Compatibility rating, and that's an F. That is, it does not even run under any user that does not have administrator privileges. If you're looking for well-coded software, look elsewhere.

Friday, April 14, 2006

Caveat

Just saw a post in a programming forum that I thought deserved a public service announcement. Now, I'm no math genius; calculus and linear algebra is about as far as my brain goes, and I don't get some of the proofs and formula derivations in them. But if you're having trouble reasoning out a high school algebra problem, you should probably rethink a career in computer science.

OWNED

Just saw this ancient entry on John Bell's blog (not quoted because quoting automatically applies italic, which could make this very confusing at one part). Too bad it was only his imagination :P

Dear Gang,
What a funny letter I got on my wewantcatherinebelliniraq@yahoo.com account and yes I check it. At first, I'm thinking, Oh oh, the name on this letter has a familiar ring to it. I opened it up and it's one of those scams to try to sucker you out of cash etc. What a relief it wasn't the brother of the guy I was making fun of with the bad breath who flew with me last week. Well I was a little bored and ordered up a patrol of four M-1's Tanks and a squad of Marines to go claim my 10.5 million dollars that this future MAMS is hiding in Asia or his house. Boy you should have seen the looks of all the people along the streets as we rolled down Asi Salman street right up to number 24A Idrisa Rd. I jumped down off this tank and ran up to the front door rapping on this giant knocker made out of an old mortar. (Clue something is amiss)
Me, "Hello, are you Aminu Ali Hassan?"
Huh? Me, the son of the traitor Chemical Ali? No I have never heard of him"
Looking down I notice a Fedex box from Jordan with Bio Chemical stickers all over it.
Is that your box with the name Aminu Ali Hassan on it? Looking very incredulous (big word for a Marine) he cocks his head and says "no, not me, must be mistake, they drop off stuff to the wrong houses all the time here" Now he is very nervous as the turret on the tank start turning towards us. "I do not understand, why are you here sir?" I pull out my email shown below, "I'm here to collect my 10 million, or didn't you think about it when you sent it to a Marine whose stationed down the street?" My future business partner looks at the email and starts to frown as if he's seen this before, He calls to his son, Blah blah blah, I don't understand but I know that tone of a mad father. His son comes out and the father says. "you are not here for me, but my son, he is the guilty party. Ever since Saddam left, we have to put up with call waiting, cable t.v. and computers. My Son didn't mean anything by it, but I was starting to wonder how he bought that new BMW out there. Ah kids eh' they never change. "same with parents" I'm thinking.
The door to the office opens as I stare at my email and Sgt. Warren says "Hey Sir, are you ready to go to chow?" Back to reality from my Walter Mitty day dream. What a dream, 10 million… Anyway check the letter out below.

From Aminu Ali Hassan
Home Address:
No 24A Idrisa Road,
Bagdad, Iraq.
[I wish this guy lived here, I would go knock on his door]
Dear , Friend
[He failed out of English 101 with all the Football players from my old school.]

Wa-Salaam w'Ala ikum, walhamdililahi wabarakato, I hope you are in [Sounds greek to me] Peace of our dear Allah, May he Bless you abundantly.? .

I am Aminu Ali Hassan, the only child and the only son to Late Haji Abdul Hassan, well known as chief protocal officer to Ali Hasan Al-Majid "Chemical Ali". I [no spell checker on his computer] am 25 years old. My late parents were killed during the U.S air raid in bagdad early 2003.My late fathe was well trusted by Hassan Al-majid, [can't even spell Baghdad, my first clue about the guy who wrote this]

Before my father died, he deposited the sum of US$ 10.5 Million in the [10 million, man I could buy the whole country of Somalia with that.] vault of a security/finance company in Asia. Immediately I found you in [See I told you the bad guys read these posts, see how he found me???]
internet I felt you can be of help to me. That's why I am sending you [Of course the Marines would love to help you out…] this email. I need someone who has the capacity to receive such huge [I think the IRS would have something to say about large sums showing up] amount of money in his account and I am willing to give up some reasonable part of the total amount to you. I want to set up some business investment with this money outside Iraq and for this reason, I lok forward to further cooperation from you and will be grateful [Spelling is kicking his butt...see he's a roadie needing more money for the next grateful dead show] for your immediate response Please send your reply to my private e-mail [sorry Eminu, I don't reply to IamAnIdiot@yahool.com …]

address
Yours Sincerely,
Aminu Ali Hassan.

Thursday, April 13, 2006

Sucks to Be Them

Doing some research, and came upon this quote from one article (note that they would have been the first person to come up with a lock-free resizable hash table):
After the initial design, it took us several years to establish the safety properties of the algorithm. We did this by means of the proof assistant PVS [23]. Upon completion of this proof, we learned that a lock-free resizable hash table based on chaining was proposed in [25].

What Is It Good For?

So, a couple people have been asking what the advantage of atomic structures is over simple traditional structures (like STL) and a mutex. Speed is the primary reason. Atomic structures are slightly slower than their traditional counterparts when only a single thread is using them (the best case scenario), but quickly make up for this in multithreaded programs.

Mutexes, by definition, are mutually exclusive. Only a single thread may hold one, and any additional threads trying to get it have to get in line and wait their turn. Now, doing something with a data structure inside a mutex doesn't take that many cycles (I'd estimate about 500, if a memory allocation is required), but that's still completely dead time.

The real killer, however, is the possibility of going into wait. Suppose A holds a mutex and B wants that mutex. If B is lucky, it's running on a different CPU, and spinning a bit (up to 500 cycles) will succeed in waiting A out. But if there's only a single processor, spinning is out of the question. Worse yet, A could have its time slice expire inside the mutex, and now B will have to wait tens or hundreds of thousands of cycles (which is way beyond any reasonable spin limit), prompting it having to wait on the mutex.

Once B has to wait on the mutex, any hope of a speedy trial is over. Once you give up the CPU, Gord knows when you'll get it back (even in the best case it will likely take more than 10,000 cycles). Even worse, if A gets preempted in the mutex, that causes two wait equivalents: one for A to get the CPU again, and one for B to get the CPU after A leaves the mutex. These problems only get worse if there's a thread C or D also waiting for the mutex.

So, what can lock-free structures do? Lock-free means, by definition, that at any given time, one of the threads attempting to perform an operation will succeed in a constant number of cycles that make up 1 iteration (atomic structures are implemented in AtomicCompareExchange loops). For the atomic stack, the simplest of the structures (because only a single iteration failure point exists), each thread that didn't get it on the first try will have to spin, in the worst case, x iterations, where x is the number of threads that have some CPU attempting an operation on the same structure at the same time. If my logic is correct, this can be solved to yield the formula that the total amount of dead time (dead iterations between all threads), in the worst case, is O(x^3), where x is the number of CPUs in the system. In the average case, only 1 or 2 CPUs will be attempting operations at the same time, which means 0 and 1 dead iterations, respectively. The other atomic structures are more complicated, and I'm not certain how to calculate the complexity of them in the worst case (math never was my strong suit).

In addition to being a dramatic improvement in dead time, there are some cases where threads absolutely cannot wait. These are mainly hardware-linked real-time threads. For example, one day BZ asked me for help with a problem he was having, where he needed to dequeue something from a shared structure in a hardware feeder thread (the thread fetches data for the hardware, and so has a very limited amount of time it can take to get that data). In this case, going into wait means death. That leaves only the possibility of lock-free (or, even better, wait-free) structures.

There is a stronger version of lock-free algorithms called wait-free algorithms. Wait-free algorithms provide an additional guarantee: that threads attempting an operation will complete that operation in the same order they started the operation (unlike lock-free algorithms, which only guarantee an upper limit on the number of failed attempts for a thread). However, wait-free structures are far more difficult to design than lock-free structures, which are already far more difficult to design than thread-unsafe structures. I only have an algorithm for a wait-free implementation of load/store with reserve.

Status Report

Atomic stack and atomic queue are complete, and working by my tests (although I've only tested it with a single thread, so some errors may not show up). Now I just need Merlin to proof-read them, then help me optimize them and figure out where to put memory barriers. In the mean time I'll get to work on: atomic set, atomic hash table, read/write with reserve variable template, atomic linked list, and atomic deque, possibly in that order.

Happy, happy nights ahead!

Wednesday, April 12, 2006

Perfect Nerd Evolution

So, Merlin finally got around to sending me a few articles I was looking for (actually about a week ago). A whole bunch of sweet stuff in there. Algorithms for atomic, lock-free (thread-safe without the need for a mutex/read-write lock) stacks, queues, linked lists, deques (double-ended queues), sets, hash tables, even a memory allocator. As well as algorithms for load/store with reserve (you read a variable, make some change to it, then write it back only if it hasn't been modified since you read it; if it's been modified, you start from the beginning again) on arbitrary variables (even structures larger than one processor word). Naturally I'm planning to add all/most of this to LibQ (we'll see if that ever happens).

So yeah, it's awesome. And to think I thought it was kinda pathetic when Merlin was going nuts when he found this stuff a year or two ago. I guess you can get more nerdy over time.

Incidentally, the title is a reference to The Wallflower (AKA Perfect Girl Evolution). A candidate title was Plato Lives (that's an inside joke; hopefully at least one person gets it).

Monday, April 10, 2006

Why the AVI?

So, I've had a couple people question (well, okay, it wasn't really 'questioning'...) my choice of video file formats. For those too lazy to look, the format I ultimately decided on was Microsoft MPEG-4 v2 video and MPEG Layer-3 audio in an AVI package. This was actually the product of quite a bit of research.

Being the compatability nut that I am, I first and foremost wanted a single format that both Windows and OS X could play out of the box. I looked at the list for Windows XP, the Windows Media Codecs Download Package 8.0, QuickTime, and this page. A few different possibilities showed up. Of the possibilities, MP3 was the obvious choice for audio.

For video, the choices are much more limited. QuickTime supports a fair variety of formats, but not that many than Windows XP also supports. By far the best option of the video codecs was ISO MPEG-4, supposedly supported by both. However, trying this out produced a rather ugly bug in the Windows ISO MPEG-4 codec - the codec only works when running as an administrator. I don't know the exact reason for this, but I suspect it has something to do with accessing restricted registry keys. In any case, ISO MPEG-4 was out. Failing that, I tried Microsoft Video 1; this proved far too poor quality to consider using. It was about this point when I realized that I wasn't going to find a single perfect format that works on both out of the box.

So, I applied a bit of market logic to the problem. Windows has something like 90% market share, OS X less than 5%, and Linux less than 5% as well. That made the decision pretty easy: whatever format I used had to work in Windows out of the box. I did some asking around, and found out about Windows Media Components for QuickTime. This seemed like the best available solution to the problem - run on 90% of computers out of the box, make the other 5% download a plug-in to work with the format.

Once this was decided, MS MPEG-4 became the obvious choice for the video codec. I would have used version 3, but the encoder I'm using - mencoder (with the libavcodec library) - doesn't support this.

The choice of container was semi-arbitrary. My first choice was the MP4 container, but Windows can't play that out of the box. So, I went with the old, reliable AVI.

So, that's the story; not a whole lot to it.

Forgot to Mention

Here's a little physics quiz for you: when is more energy less energy? I actually have a topic to write about involving the answer to this question; we'll see if it gets added to the list of things I plan to write about and never do :P

& More Trophies

Oh yeah. This time I've got the good stuff. Well, some of it (mostly the stuff I didn't do) more than others. Let's go through these from worst and/or least interesting to best.

First up, a demonstration of a basic step sparring combination - StepSparring.avi

Next, me breaking four boards with a jump side kick - Break2.avi; I actually was expecting to have to do five boards with a step-behind side kick, but this is what they wanted, instead. When I was getting this off the video camera, I was pretty depressed about my obvious grace (or lack thereof), until I saw that neither of the two instructors did it that much more elegantly than I did :P

Me breaking three boards with a turning kick - Break3.avi

Me breaking three boards with a punch - Break1.avi. Looking at the video, I don't use my waist as much as I should, so there's some extra power to be gained, there.

My instructor breaking four brickish things with a side kick - 4BrickBreak.avi. This would technically be considered a speed break (which is harder than other types of breaks for the same number of boards/hard objects), as neither end of the bricks is really secured. This requires dramatically greater speed to do than normal breaks, because the thing you're attacking is free to move away from you, distributing the impact over time; the only thing holding it in place for you to break is inertia. This instructor is a fourth degree black belt; he was planning on testing for fifth degree this test, but his wife wasn't ready to test for fifth degree, and asked him to wait for her.

The aforementioned master instructor (or is seventh degree considered low grand master? I'm not sure) breaking seven boards with a back kick - 7BoardBreak.avi. It wasn't caught on camera, but if you'd been at the test, you would have seen me rapidly back away from the breaking area when he got up and started walking in that direction :P

Saturday, April 08, 2006

& Trophies

And I'm back from the black belt test. Not exactly the portrait of the ideal martial artist, but I passed, which is what's important for the moment. Got some nice trophies; at least, they should be nice. My dad video-taped part of it, and took still pictures for other parts. Unfortunately, the digital camera he was using for the still shots doesn't really take pictures at a precise time (you can't expect it to take a picture within like 1/10 of a second after you press the button), so he wasn't able to get too many good still pictures; the slow shutter speed of the camera made for some sweet motion blur shots, though. I'm posting the four best still pics right now; none of them are of me doing anything (although you can see me holding boards in a couple of them):


Awesome motion blur (the best of the 42 pics, in this regard). This is a four-corner break, where you do four separate attacks in quick, fluid succession, and usually with less boards than you'd do with each attack individually; this is a front snap kick with one board. I'm the one holding the board she's kicking.


Another person's four-corner break; side kick with one board. Again, I'm the one holding the board.


And another. Apparently this shot is the leg returning to the floor after breaking two boards with a side kick. By this point I was taking a break from holding, between the twice I got kicked in the fingers by one woman, and the fact that I'd just done my four-corner break and power breaks (several individual attacks with lots of boards).


Three board power break with a middle knife hand strike. Both holders have pretty pathetic looks on their faces :P

I don't yet know how the video turned out; it looks like it's gonna take a fair bit of work to extract video from this thing with it's A/V out and encode it, and I don't really have the time to spend until like next weekend. But if it turned out well, there are three clips I want to post online: me breaking three boards with a punch, the master instructor (the 7th degree I mentioned last post) breaking seven boards with a back kick (awesome), and another instructor (the one who teaches at my school, 4th degree) breaking four bricks with a side kick (pretty cool looking).

Wednesday, April 05, 2006

& Stress

So yeah, that title pretty much says it all. A short summary of the coming week (and last couple days) for me:
- Turned in a programmingish assignment Tuesday
- Have another programmingish assignment due Thursday (not too bad)
- Have a history report to start and finish by Monday (not too good)
- Have a cumulative biochemistry test on Wednesday (bad)

So, all in all that's not too good. But that list in and of itself isn't sufficient to give me this psychosomatic stomach flu I've got right now. No, that requires the test for third degree black belt I have on Saturday (3 days from now). I only found out I was eligible for it on Monday (2 days ago), and that was around the time this stomach flu started.

This is a pretty big deal, at least for me (given a bit of history). I've been a second degree for 6 years now. Most of this is due to me simply being too lazy to put too much effort into it the last 3 years (most people are eligible to test for third degree after 3 years of being second degree, but this was after I started college, and I didn't really feel like I ought to test).

Last October (black belt tests are every 6 months) was really the first time I actually wanted to test for third (and actually put effort into getting ready for it), but I wasn't allowed to. Basically, the reason for this was that a lot of big names in the school were planning to test in two days from now (the teacher and his wife, as well as two other teachers, were going to test for fifth degree, and another student was going to test for fourth degree), and the teacher wanted me to wait and test with all the others.

The other reason was that I didn't pre-test the test before that. That normally wouldn't have been significant (I had pre-tested way more times than I needed - five - before that). What happened was that the school was sold to a new teacher a bit before that, and he wanted me to pre-test for him before finally testing for third.

So, that was pretty disappointing. Anyway, I'm testing now, and way more freaked out than I should be. The test will consist of six parts: patterns, terminology, sparring, board-breaking, step-sparring, and self-defense.

Patterns (called 'katas' in another martial art - I think karate) are sort of dances of sequences of martial arts moves (I'm being really vague here because lots of different martial arts have them). Besides being neat-looking, these are used to practice the moves in them. To do a pattern well requires that you have both strength and good (elegant) form in all the moves. Some various other things are attached, as well. Each pattern has some historical meaning, and may have some metaphorical parts to it (for example, one common metaphor is to end a pattern with a left-handed attack to symbolize the unfortunate death of the person the pattern is about). For a full test you're supposed to know all patterns up through your belt level (a total of 15, in my case)

Terminology is basic memorize and recite. You need to know the meanings of all the patterns for your belt level (and the meanings for all the lower ones, if your instructor feels like asking you them). In addition, you also have to know a bunch of Korean (in this particular instance) words, such as all the names of the moves and objects and events in the school, counting to 50 (in Korean), etc.

Sparring and board-breaking are pretty obvious, not to mention enjoyable (sarcasm). I'll probably have to break five boards with a side kick, three boards with a punch, three or four (at least I hope not five...) with a back kick, and two boards with a reverse hooking kick. Or, if I'm really lucky, it won't be boards at all; the teacher has been playing around with bricks and ceramic roof tiles (these tiles are curved, making them much stronger than they would be if they were flat, and several times stronger than boards) the last couple weeks...

I should mention that these are stock boards (10" x 12" x 1/2" slices) taken from the nearest Home Depot (or comparable store). They may be picked over so as to not use pieces with knots (unless you're unlucky...), but they're not treated in any way to make them brittle. I had the unpleasant experience once of being one of the holders for the highest ranking student (not grand master) in our school (was sixth degree at the time, now seventh) - 7 boards with his specialty - a jump back kick. Seven boards is a fair bit more than you can get your fingers around, which was actually a good thing, considering basically my entire palms got bruised from that :P (for those wondering what that looked like, there were two of us that actually held the boards, and four people who held our wrists, for reinforcement)

Step-sparring and self-defense are more or less canned counterattack combinations for common scenarios. These are responses either to attacks (step-sparring, where usually the attack is a punch) or someone grabbing/restraining/choking you (self-defense). Unlike much of the stuff in martial arts (at least in modern, sporty martial arts), these are intended to seriously injure or incapacitate somebody, using such things as strikes to the neck, attacks to the groin, or breaking of joints. You don't practice these at full strength :P

So, that's the basic rundown. And now I'd better be getting to bed; I have a lot to do this next week :P

Sunday, March 26, 2006

Kids (and Computers) Say the Darndest Things

The last day or two I've been working on the successor to Trans-Roman Alpha (I should blog about this, sometime...): Trans-Roman Beta. Well, so far all I've done is play around with algorithms some; one algorithm in particular reads in an amount of text in some actual language, learns the rules of how that language constructs words to the best of its ability, and then generates random gibberish that imitates the language it was fed.

In addition to the practical value of this algorithm, it's also good for laughs. Initially I fed it the English translation of War and Peace, but it often ended up in infinite loops, using that as its data set. So I decided to feed it an English dictionary, instead. That allowed it to generate a wide variety of gibberish, sometimes actual English words, sometimes humorous words, and sometimes neither of those. Below is a list of some of the ones I found amusing, from a total of 50,000 characters it generated (keep in mind that this is random with regard to each character generated):

goatempts curvaccidatodgy zeppasmo almly zookelpful quinedibly votrepinabitized czarskiing qweryphs zuccon xercococcur forkplay fruckage beepfat qualmly wussyfoo gluejew qwerbage weenie feelworldvic vyingfishpad squettled jarfed clatchfin owlywed xylorying frazziest pornumb bromsdam sunkyard fryingpie menhand xersnigget twirlifted gyroite yowlywed zomboide gagiosex knivie runtnest fobbyhoe dogey glasmanly ptoriery

I've also noticed that this thing suffers from occasional dictionary poisoning. That is, it'll see some odd word once ('qwerty' comes readily to mind) and it'll start using structures from that word all over the place, even if no other word in the dictionary uses said structures (for example, it became quite fond of starting words with 'qwer', despite the fact that 'qwerty' is the ONLY word in the dictionary that has this). So, I guess in a way this is like having a little kid :P

Incidentally, 'xersnigget' might be my all-time favorite "word".

Saturday, March 25, 2006

My Program Is Mocking Me...

FusionReactorII says:
Ah crap
FusionReactorII says:
That won't work
FusionReactorII says:
Well, it works for generating random text. But it won't work for Trans-Roman Beta, because it needs to be reversible
Josh says:
heh
FusionReactorII says:
I wonder what would happen if...
FusionReactorII says:
LOFL
FusionReactorII says:
That totally broke it
FusionReactorII says:
You've got to come see what it generated (because it broke)! That's absolutely hysterical!
Josh says:
sec

Thursday, March 23, 2006

Windows Internals Curriculum Resource Kit

I've just found something godly: the Windows Operating System Internals Curriculum Resource Kit by Microsoft. It's basically a university course on Windows internals, complete with lectures, labs, quizzes, homework, etc. The material seems to be derived from a number of wildly popular Windows system and internals books, and adapted into a university course by a pair of professors; Microsoft then licensed the material and is distributing it free.

There's even a lecture comparing and contrasting the Windows and Linux kernels.

Now go! Fetch!

Wednesday, March 22, 2006

It's a Wonderful Life

So, I've now had midterms in every one of my classes this semester - biochemistry, biology, biology lab, computer science, and history. It seems this semester I'm having extraordinarily bad luck at getting teachers with both a good sense of logic and a good sense of time.

The first of these tests was in biochemistry. The teacher had very clearly said, about a week before the test, what material would and would not be on the test (that is, none of the stuff in lecture less than a week before the test would be on the test). She even very specifically listed a couple topics in particular that would not be on the test. Guess what was worth 15% of the grade on the test? However, when she saw that I'd written on the test that she said that wouldn't be on the test, she decided to multiple everyone's test scores by 1/0.85.

But that wasn't the only problem. I noticed that at the end of the test, when she told everybody to turn in their tests now, only 3 or 4 people (out of a class of at least 30) had left early. I reasoned that if only 10% of the class had left early, that probably meant that a good 65%+ of the class or more hadn't even finished the test. I sent her an e-mail to that effect, saying that the test was too long. I got back this reply (actual quote taken from the e-mail):

at least 30-40% of the class had finished the test before time was up thus I do not believe that there was any problem with the length of the exam (except that it was probably too short)...

Okay, moving on...

Next up: biology. This test had more or less the same problem, only worse: few, if any, of the students had time to complete the test (indeed, after we handed in the tests I heart just about everybody at my table complaining that they weren't done). On the test was a wide variety of questions, but one, worth about 20% of the test (which means you should be able to answer it in about 20 minutes), was really the deathblow to reason and sanity. It went something like this (recalling from memory):

You are working in a barn, and sit down for a moment. When you sit down, you find that you've sat on a rusty nail, and deeply impaled yourself. An additional concern to you is that you have previously had a skin infection, which might have managed to get in the wound. Explain how the immune system would respond to this, including specific cells, locations of occurrence, chemicals, and chemical receptors.

Okay... macrophages, neutrophils, cytokines, inflammation, complement, lymph system, phagocytosis, antigen presentation, B-cell proliferation/differentiation, memory cells, plasma cells, antibody production, and a few other assorted things. Well that answer covers a good 2/3 of everything we'd learned in class up till the test. A succinct person like myself might be able to squish the answer into 3 full pages (had I had the time); other students had already gone beyond that before running out of time (and still didn't get near all of it covered). Honestly, this is about as much material as I expected to have to recite on the entire test; but then, maybe I'm too sane to be a teacher.

Next up was computer science. Nothing much to see here, other than more of the same: too freakin long. Again only 2 or 3 people out of a class of at least 30 had turned in their tests before being forced to, and again I heard people all over the room saying "I didn't have time to finish!" Somehow (probably due to the fact that 2 out of 2 of the previous tests had been this way) this wasn't so very surprising.

This was the same test that one grammar question was on; the teacher is a pretty cool guy (imagine a slightly nerdy Howie Mandel; he even looks like Howie Mandel), but he really could stand to get a handle on the fourth dimension.

Next was the history test. This was the only one of the tests that I was actually satisfied with my answers (and didn't feel like I could have done better if I'd had more time). Although a bit of that is due to the fact that we knew exactly what was on the test before we took it; the teacher made a study guide (about 3 times as long as the test) which included all of the questions on the test, as well as about twice as many questions that weren't (though we didn't know which was which ahead of time).

Then today came the biology lab test. This test seemed to be the worst of all of them, but that could just be because I've forgotten some of the specifics of other tests (which were 1-2 weeks ago). As this post is already way too long, I'll limit my complaints to only a few of the problems with this test. Let's start with this gem (rough recall of the question from memory: "Explain what the difference between confocal microscopy and fluorescent microscopy is, and the advantages of confocal microscopy." Mu? How does one explain the difference (and the superiority/inferiority) between two things that aren't mutually exclusive?

A second example (the last one, as this post is already hideously long) is one involving a graph of "precipitation" (no units given) vs. "antigen" (mg). The question asks you to calculate how much antibody there is at a given point in the graph, giving the answer in mg/ml. A bit of explanation is in order for this. This is a graph you would make using a spectrophotometer (hence the lack of units for the y axis); you would then use a standard curve to calculate the concentration of the unknown based on its absorption. Usually the x axis is in mg/ml, but this could be calculated if the volume was known (since the weight is known). I go up to the teacher, and the dialog goes something like this:

Me: There isn't enough information to answer this problem
Her: Huh? Never had a problem with it before...
Me: This graph and the data table are in mg. The answer requires the volume to be known, and it isn't given in the question.
Her: *takes a minute or two to look over the question* Oh. Well, I guess just assume that was supposed to be "mg/ml".
Me: Also, this y axis of this graph has no units
Her: So? That's how we always do it.
Me: We always have a standard curve. There is no standard curve here.
Her: *takes a minute or two to look at the question* Oh. I guess that axis would have to be mg/ml, then.
If you're looking to get a space craft to Mars, I can give you the name of somebody not to employ.

Tuesday, March 21, 2006

The Solution

Alright, let's see if I can get through writing this post without my computer blue-screening (again).

The reason this question was so cool is that it's not only hard (1 in 25 isn't very much), but the solution is extremely simple and elegant (at least in concept; when written out in grammar it isn't so pretty): it's a simple deterministic 4-state machine, represented by the following graph:

The machine begins in the even 0s and even 1s state, and changes state each time it reads a bit in the number (the order it does this doesn't matter). If at the end of the string the state is even 0s and odd 1s, then the number is valid. This machine can be directly expressed in grammar, but it can be a bit cumbersome to read; thus why I've only given the graph.

As a bonus, this next graph shows a machine for the same problem, save that it's 0-exclusive: it isn't valid to have zero 0s and odd 1s.

Oh, and on an unrelated note, I just learned that Windows Vista has new API functions for read-write locks and condition variables. Also, NT 3.5+ has undocumented but stable functions for read-write locks. I'll have to see about adding support for those in LibQ at some point (heck, I'll have to see about doing anything with LibQ at some point). For those of you wondering, the complete lack of content lately has been due to me getting back into WoW after a couple month break :P

Friday, March 17, 2006

MSDNAA is Godly

So I just got hooked up with Microsoft Developer Network Academic Alliance through my school. I more or less downloaded everything they had up there, including Windows 2000 Pro, Windows XP Pro, Windows Server 2003 Enterprise (!!), Visio 2003 Pro, Project 2003 Pro, Visual Studio 6.0 Pro, and Visual Studio 2005 Pro (KAITY). Nothing like waking up and finding like 5 grand of software legally at your fingertips for free!

Oh yeah, and I used Visio to make a beautiful diagram of the solution to that grammar problem. I'll post it this weekend, so you better try it before then! :P

Wednesday, March 15, 2006

The Challenge

I just had my first test in High Level Languages, a third-year course about the structures common to most/all high level languages, and how high level languages in general work. I thought one of the questions on the test was absolutely godly (and from what the teacher said, I was the only one in the class who figured out how to do it; however, I don't know if this is because nobody could figure out how to do it, or they made some critical typographical errors in their answers). I suggest you try and solve it, because it's an awesome question. It goes like this:

Create a grammar (BNF, EBNF, syntax diagram, whatever kind of formal metalanguage you want) rule for binary numbers of any length, containing an even number of 0s (0 inclusive) and an odd number of 1s, in any order.
You have fifteen minutes. Go!

Saturday, February 11, 2006

Real Life Adventures - Salva Nos - Part 2

1: Dominus* Deus
2: exaudi nos et miserere
3: exaudi, Dominus*

4: Dona nobis pacem
5: et salva nos a* hostibus
6: Salva nos, Deus

7: Dominus* exaudi nos
8: Dominus* miserere
9: Dona nobis pacem
10: Sanctus, Gloria

11: dona nobis pacem
12: et dona eis requiem
13: inter ovas* locum
14: voca me cum benedictis
15: pie jesu domine, dona eis requiem
16: dominus* deus, Sanctus, Gloria

Looking at the lyrics, there are two distinct themes that seem odd to encounter in the same song. While the entire song is speaking to God, one refers to 'us' - 'hear us', 'have mercy on us', 'save us', 'give us peace'. The second theme (lines 12 and 15) refers to 'them' - 'give them rest'. For this reason, I'd initially thought that there were two sources. Well, it turned out that I was right... sort of.

Lines 12 and 15 sound very much like a Catholic funeral mass, so that's where I started looking. It turns out that this is exactly what it was - a part of the Dies Irae ('Day of Wrath'), a poem incorporated into the funeral mass (for translations, see the Wikipedia article):

Lacrimosa dies illa,
qua resurget ex favilla

judicandus homo reus.
Huic ergo parce, Deus:

pie Jesu Domine,
dona eis requiem. Amen.

Interestingly, a couple different passages also appears in the poem (don't assume these lines are all consecutive):

Rex tremendæ majestatis,
qui salvandos salvas gratis,
salva me, fons pietatis.

Inter oves locum præsta,
et ab hædis me sequestra,
statuens in parte dextra.

Confutatis maledictis,
flammis acribus addictis:
voca me cum benedictis.

So, there are lines 12 through 14. What about the rest? Well, save for three lines, none of the rest of the song is taken whole from any other work (that I've found). Rather, it's a weaving of passages from several other things. First of all, let's look at the first line, part of which is repeated in the last line. As I mentioned before, 'Dominus' is the nominative form, which is incorrect in this context (it should be 'Domine' - the vocative form). Yet surprisingly, it turns out that this line is taken directly from Sanctus, a part of all Catholic mass (not just funeral mass):

Sanctus, Sanctus, Sanctus,
Dominus Deus Sabaoth;
pleni sunt coeli et terra gloria tua.

Hosanna in excelsis.
Benedictus qui venit in nomine Domini.
Hosanna in excelsis

Holy, holy, holy,
Lord God of hosts;
heaven and earth are filled with Your glory.

Hosanna in the highest.
Blessed is he who comes in the name of the Lord.
Hosanna in the highest.

Okay, so. We have the original Latin, and it's still in the nominative form, even though it's speaking to God. Is my assessment wrong? It isn't, actually (not in this case, anyway). It turns out that this Latin is actually a mistranslation of Isaiah 6:3, presumably originally in Hebrew: "And they cried one to another, and said: Holy, holy, holy, the Lord God of hosts, all the earth is full of his glory". The original text was not speaking to God at all, and as such the nominative case would be appropriate. If you look at the rest of the mass program, 'Dominus' is never used again when speaking to God; it's always 'Domine'.

This error was presumably propogated to other instances of 'Dominus' in Salva Nos.

The use of 'exaudi' seems to come from the Introit of the mass service (also a part of the funeral mass):

Requiem aeternam dona eis, Domine,
et lux perpetua luceat eis.
Te decet hymnus Deus, in Sion,
et tibi reddetur votum in Ierusalem.
Exaudi orationem meam;
ad te omnis caro veniet.

So, that's as far as the funeral mass can take us in this study. This leaves us still with three phrases. To my surprise, two of these may be found in Agnus Dei, another passage in the mass. This did not come to my attention when looking at the funeral mass, because the two phrases are missing (actually replaced by other phrases) in the funeral mass version:

Agnus Dei, qui tollis peccata mundi, miserere nobis
Agnus Dei, qui tollis peccata mundi, miserere nobis
Agnus Dei, qui tollis peccata mundi, dona nobis pacem

That just leaves one word - 'hostibus' ('enemies'). This one I'm not so sure of. The exact word does not appear in either the ordinary mass or funeral mass ('hostias' is a different word - 'sacrifices'). And looking for a document that was read by the author of the song when you only know a single word in it is like looking for a needle in a haystack; I think I'm gonna let that one go.

Lastly, I probably prompted a couple questions in my study, such as why the erroneous words (indicated by asterisks) have changed. First of all, 'a' - 'from' - is incorrect. Yes, 'a' does indeed mean 'from'; but from what I've been able to tell, 'a' changes to 'ab' when used before a word that begins with a vowel sound (try searching for "a hostibus" and "ab hostibus").

The big one, of course, is 'salva'. It turns out that 'salvo' is indeed a verb. Given the way it was used in the song (the fact that it was using a different conjugation system, and that it was used as a transitive verb), I was beginning to wonder if this might be the case. It seems to be an uncommon word, as most dictionaries don't have it (I've only been able to find one dictionary online to date that does).

So, I think that's the end of my report. If you haven't noticed by now, I've color-coded the lyrics so that their origins can be easily seen in the passages I've quoted. Thanks to John Briggs and Johannes Patruus for answering my Latin questions.

Friday, February 10, 2006

Real Life Adventures - Salva Nos - Part 1

Recently I've been listening to the music of Noir, an anime I like (although the ending kind of sucked), its music composed by my beloved Yuki Kajiura. I quickly came to like one song in particular, called Salva Nos. Eventually I started to wonder what the lyrics were (noticing a pattern, here?), as the operatic style makes it difficult to distinguish the words by ear. A quick search on Google turned up a listing on Anime Lyrics (I've modified them a bit because I think there were errors in the original transcript, and I've included my rationale for these changes in brackets).

Dominus* Deus
exaudi nos et miserere [singular imperative form of 'misereor' - have pity]
exaudi, Dominus*

Dona nobis pacem
et salva* nos a hostibus
Salva* nos, Deus

Dominus* exaudi nos
Dominus* miserere
Dona nobis pacem
Sanctus, Gloria

dona nobis pacem
et ['and'] dona eis requiem
inter ovas* locum
voca me cum benedictis
pie jesu domine, dona eis requiem
dominus* deus, Sanctus, Gloria

Anyone who has seen such a thing before will immediately recognize this as Latin. It looks like a Christian hymn, based on the subject matter; either a real hymn (as in, written back when Latin was still common in the church) or an imitation made to sound like a real one. At first I suspected it was the latter, until I read the lyrics near the end of the song. Much to my surprise, there was a reference to Jesus by name. This is such a surprise because less than 0.5% of Japanese are Christian, and a good majority doesn't even know who Jesus is; this suggested that perhaps it was a real Christian hymn, after all.

So, how to tell the difference? Well, the first solution that came to mind was to check if it was proper Latin grammar. If the grammar was flawless, it was probably written by someone fluent in Latin, such as a native speaker or a priest of the church. If it was badly bastardized, it was probably written by Kajiura herself (for comparison, take a look at the lyrics to Maze, by the same composer).

Now, checking Latin grammar isn't hard... if you know Latin. Unfortunately, my knowledge of Latin consists of a few dozen words along with my knowledge of Spanish (a Latin derivative, which often resembles Latin). That means it's time to break out my Latin-English dictionary and Quick Study Latin grammar sheet.

Okay, going through this word by word (specifically the ones I marked with asterisks, indicating that I think they're incorrect)...
Dominus: This is the nominative (sentence subject) form of 'lord'. The correct form for direct address would be 'domine'. I don't know whether Deus is kept the same for the direct address form or not.
Salva: This is the Spanish/Portuguese form. 'Salvar' means 'save', and the conjugation is imperative. However, in Latin 'salveo' is more of a passive voice - 'be well' or 'be safe' (it also is an intransitive verb). The correct word in Latin is 'servo', conjugated as 'serva.'
Ovas: A form of 'ovis' - 'sheep' - referring to God's sheep (the church). The correct conjugation would be either 'ovibus' or 'oves' (I don't know whether the accusative or ablative form would be correct, here).

Okay, so, that makes it seem likely that this is not a real hymn; that leaves the question of where the lyrics came from. As mentioned previously, most Japanese don't know who Jesus is, so it would be improbable that this was written by somebody who is Japanese. Well, let's look for other clues...