Letters, Words, and Big Numbers, Oh My!

So, I was bored and... decided to play around with license keys some. Everybody hates license keys, right? Especially in cases like Neverwinter Nights, where they have 35 alphanumeric characters (!). We're currently in the process of making some changes to how the system works at work, and one of the results is that we'll now be using license keys for something. So, what can we do to make them more friendly?

Let's apply some basic psychology to the problem: the brain only has so many registers (bits of information that it can hold readily available without requiring effort to memorize the information; I think the exact number is like 5), with each one able to hold a symbol (remember that the brain's processing abilities are highly symbolic). For a random alphanumeric string, each character must be stored in a separate register (if you think that's dehumanizing, you should see the occasional debates me, DB, and BZ - all of us programmers, but all of us also interested in biology - have on the topic of reproduction and evolutionary psychology; and yes, I am aware that "me" isn't technically a subjective pronoun). For a string of, say, numbers where a pattern is evident, the brain can apply compression to the string, and store a larger number of numbers in its registers than it would be able to if there was no pattern.

So, my idea is simply this: use symbols larger than letters and numbers in the license key. This one dictionary I picked for this purpose has 16,100 English words of 7 characters or less (a somewhat arbitrary limitation I established), and that's not even including conjugations of most verbs.

Let's see how well this works. If we take the NWN key, the maximum number of theoretically possible keys is about 3*10^54 (36^35; quiz: how many bits is that?). I can remember about 5 characters at a time, meaning I will have to look at the key 7 times to type it in, if I don't type as I'm reading it (which is reasonable for people who aren't secretaries or programmers). It would take 13 words to represent this key (log(36^35) / log (16,100)). I can remember about 4 of these words at a time, meaning I can type them in 3-4 groups, almost half as many as for the string of random characters.

However, there's one more thing to consider, which is actually a facet of something already mentioned: most people aren't secretaries or programmers. They probably can't type even half as quickly as I can. In addition to the previously stated implications, this also means that they're going to have at least twice as long as I do to remember the words/characters, and 13 words would be a total of 75 characters (average word length of 5.75 letters). And unlike registers in a CPU, the brain's registers lose the information they were holding fairly quickly. Unfortunately, I don't really have any way of quantifying this effect, like I was able to benchmark how much I could remember and type in, so this really remains an unknown.

& Linguistics - Case - Japanese 2

Anyway, getting back to the topic of the series, Japanese is unusual in (at least) one more way: it does not use case at all. Well, not technically, anyway. Instead, Japanese has about ten half-cases indicated by postposition (the opposite of prepositions) particles.

The emphatic nominative case (my name for it) is indicated by the postposition "ga", as in "anata wa watashi ga doko nimo inai to omotteru" ("You think that I don't exist"; you can get additional meaning out of this sentence after reading the next paragraph). This is like the nominative case, but it carries an additional property - it serves to emphasize the subject as opposed to the predicate (this is not clearly illustrated in the example).

The referential case (also my name; sometimes called the absolute case) is indicated by "wa". The referential case can be used in several ways. It can be used for the subject of the sentence, where the predicate is more important than the subject; kind of a "non-emphatic nominative" case. But it can also be used to set the point of reference of the sentence, which might not be the same as the subject; this would be translated as "with regard to" or "as for". This distinction is beautifully illustrated by "anata wa kodoku ga koko kara kieru to omotteru" ("I think that the loneliness [that] you [feel] will disappear from now on"; more literally, "for you, [the] loneliness will disappear from now on, [I] think").

"no" indicates the genitive case. Fully understanding the Japanese genitive case requires a small shift in paradigm. The genitive case conveys the general thought of "of", in its various meanings. This can either be in terms of possession (e.g. "hoshi no michibiki" - "star's guidance"), origin (e.g. "hontou no watashi" - "real me" or "me of reality") or distinguishing quality (e.g. "mizuiro no lute" - "light blue lute" or "lute of light blue"), reason or benefactor (e.g. "oya no mo" - "mourning for parents" or "mourning of parents"). The first three are nothing we haven't seen before in other common languages, but the last two (known as the benefactive or causative cases in other languages) are not like the genitive of previous languages.

The accusative case is indicated by "wo" (or "o"). This is trivial, and exactly like what we've seen previously (e.g. "tamashii no hanashi wo kikasete yo" - "Tell [me] the story of your soul"; "yo" indicates a request). However, when translating between English and Japanese, this can be a bit tricky, because we are used to some English verbs being intransitive and requiring a preposition, where the corresponding verbs are transitive in Japanese, and do not require a postposition.

"ni" indicates the locative case. This case represents the idea of being at some general position in space or time - either at, in, on, or around. This has a couple meanings. With verbs of existence, the meaning of position is used (e.g. "sora ni aru tobira" - "door [that is] in the sky").

This idea of position is applied in a similar but slightly different manner to yield the second meaning - that of recipient. In English we have the concept of having something on you - that is, possessing something; Japanese does, as well. In Japanese, "ni" is also used to indicate the target of a verb of transfer of possession. Think about it like this: in Japanese, you don't give something to someone - you put it on someone. In other words, the locative case is used where other languages would use the dative case (e.g. "kodomo ni yaru" - "give to [the] child").

(part 2 of 3)

& Linguistics - Case - Japanese 1 (UPDATED)

So, last post I discussed Finnish, a language unusual in that it has an overabundance of grammatical cases (far too many, as far as I'm concerned). This time I'm going to discuss an all-around unusual language (at least to us English/romance-language speakers): Japanese.

Japanese does a great many things notably differently than the languages common on this hemisphere. For example, unlike English, where every clause (save for imperative sentences) must have a subject, in Japanese it is perfectly acceptable (if not likely) for a sentence to lack a subject. Nor is it like romance languages, where the subject is implied in the verb, as the verb is inflected (it is written/spoken differently in different circumstances - declension is one type of inflection) for what pronoun the sentence refers to; no, Japanese sentences can totally and completely lack a subject, leaving listeners to deduce the subject from other sentences.

Japanese sentences are usually written/spoken in reverse-Polish (henceforth known as "Japanese") notation. If you picture a sentence as a syntax tree, child nodes are usually written preceding their parents in the tree, with the sentence ending with the verb and any sentence suffix, such as "ka" (indicating a question). For example, "mienai basho made hashiru nara" - "If you run to the unseen place" - literally "[you] not-seen place to run if".

Japanese completely lacks any dedicated personal pronouns. There are no words like "he", "she", etc. Instead, it commandeers a number of common nouns for this purpose, some examples being "watashi" ("selfishness") and "boku" ("servant" - used specifically by males) for the first person, or "kimi" ("prince") and "anata" ("over there" - something of a literal translation of "Hey, you!" although not as rude) for the second person.

Japanese also lacks grammatical gender and number. That is, it does not inflect its nouns, adjectives, or verbs based on the gender or number of the noun. For comparison, romance languages inflect nouns, adjectives, and verbs based on both gender and number; English, however, only inflects its nouns and verbs by number.

Japanese completely lacks articles, like Latin (but unlike English, Spanish, or Portuguese). But perhaps the oddest quality is that adjectives are half-verbs. It's possible to conjugate adjectives like verbs - complete with tense - and they are able to completely take the place of verbs in a sentence.

& Linguistcs - Case - Finnish

So, for the last two posts in this series, I've got a couple languages unlike the ones already discussed (at least with respect to case). This post's topic is Finnish, a language different in that it relies much less on prepositions than any of the languages mentioned so far. This is possible due to a large number of cases that fill the role that would otherwise be filled using prepositions.

Finnish declines its nouns, pronouns and adjectives, and a number of disputed cases exist, where it is debatable whether they are actual cases, or merely forms of creating adverbs from adjectives or nouns.

The definitive cases in Finnish are *takes a deep breath*: nominative, genitive, accusative, partitive, inessive, elative, illative, adessive, ablative, allative, essive, translative, translative, abessive, and comitative.

The accusative case is slightly different in meaning than the accusative of the other languages we have examined. In Finnish, the accusative case refers to the direct object, where the entirety of the direct object is involved in the action. This is in contrast to the partitive case, which refers either to a portion of a single object, to a number of objects which are a portion of a greater number of objects, or to an incomplete action.

The inessive case of an object (or even a point in time) refers to something else being contained inside that object (think of "in"; or "at" or "on", with respect to a point in time). Similarly but distinctly, the adessive case refers to existence near some object, such as "on", "near", or "around".

The elative case implies movement out of an object or a point in time (think of "out of", "from", or "since"). The illative indicates just the opposite: movement into an object or a point in time (such as "into" or "until").

Similarly, the ablative case conveys movement off the surface of an object, such as "off of" or "from". The allative is the opposite, indicating movement onto an object, such as "onto", "to", and "for". Both may be used to also indicate a change in possession.

The essive case seems to indicate a temporary state, or partition of time in which some action occurs (think "as", "when", "on", "in", etc.); looking at some examples of the essive case, it is not wholly clear to me how this differs from some of the other cases. The translative case indicates a change in state, property, or composition, corresponding to "into" or "to". The abessive case seems to be dying out in the language, and indicates the lack of something (essentially "without"). Finally, the instructive case indicates a means of action, such as "with", "by", or "using".

15 in all. Man, that's way too many cases. I'm tired out just from writing about them :P Note also that I've tried to give a description of the cases in an intuitive manner, reducing each to a single concept, perhaps applied in different ways. But some cases also have uses that aren't intuitive (at least not to me).

& Linguistics - Case - Spanish/Portuguese

Last post we looked at the decline of the English language (pun intended, I'm afraid); this post we'll look at the decline of the Latin language. What exactly do I mean by 'decline'? Well, exactly what I mentioned at the end of the last post: the simplification of grammar in languages over time.

Now, Latin is a dead language, but its derivatives live on. The flavor of the day: Portuguese and Spanish. Very much like English, Spanish and Portuguese have almost entirely given up the system of declension. Adjectives have completely lost the system of declension (although, unlike English, adjectives are still inflected based on gender and number of the noun they modify), as have nouns (an even more radical decline than English, which retains two distinct cases for nouns).

Spanish and Portuguese pronouns come in six cases: nominative (e.g. yo/eu), genitive (e.g. mi/meu), accusative (e.g. me/me), dative (e.g. me/me), ablative (e.g. mí/mim), and comitative (e.g. migo/migo). The first five are roughly equivalent to the same cases in Latin (the ablative is only different in that it can't imply pronouns as the ablative case in Latin can), but the last one is a bit more interesting.

Reading on the subject the last couple days, I found that Latin had something of a comitative half-case. The comitative case indicates "along with" or "in the presence of". In Latin this case is something of a stub: the preposition "cum" ("with") is appended to the end of the ablative form of the pronoun, as in tecum ("with you"). So the story goes, over the centuries this -cum suffix has degraded to -go, in Spanish and Portuguese, to form the modern comitative case. However, despite the fact that the Spanish/Portuguese comitative case is only used when referring to the presence of something, it still requires the preposition con/com ("with).

That's the accepted explanation, anyway; and perhaps the correct one. But while I was doing my research, I came across something very interesting. The comitative case also exists in Estonian, an east-European language. In Estonian, the comitative case is formed by adding the suffix -ga to either the genitive or the partitive case. Maybe that's just coincidence, but you've got to admit the probability of two languages using very similar form for the same function by pure chance is rather low; enough to be intriguing.

Freakin' Awesome

Saw this on Slashdot earlier today:

Researchers led by the Institute of Cognitive Science and Technology in Italy are developing robots that evolve their own language, bypassing the limits of imposing human rule-based communication.
...

The most important aspect is how it learns to communicate and interact. Whereas we humans use the word ‘ball’ to refer to a ball, the AIBO dogs start from scratch to develop common agreement on a word to use to refer the ball. They also develop the language structures to express, for instance, that the ball is rolling to the left. The researchers achieved this through instilling their robots with a sense of ‘curiosity.’

Initially programmed to merely recognise stimuli from their sensors, the AIBOs learnt to distinguish between objects and how to interact with them over the course of several hours or days. The curiosity system, or ‘metabrain,’ continually forced the AIBOs to look for new and more challenging tasks, and to give up on activities that did not appear to lead anywhere. This in turn led them to learn how to perform more complex tasks, an indication of an open-ended learning capability much like that of human children.

Also like children, the AIBOs initially started babbling aimlessly until two or more settled on a sound to describe an object or aspect of their environment, gradually building a lexicon and grammatical rules through which to communicate.

That is absolutely godly. I want a litter of those.

& Linguistics - Case - English

English is near the opposite end of the spectrum, compared to Latin, having only remnants of a previously existing case system.

Pronouns are the most vivid artifact of old English declension, having three cases: subjective, objective, and possessive. The subjective, corresponding to the Latin nominative, refers to the subject of the sentence (e.g. "I still believe that you can call out my name"); the possessive, corresponding to the Latin genitive, refers to the possessor of some other noun (e.g. "in my dearest memories"); finally, the objective, corresponding to the Latin accusative, dative, and ablative, refers to anything not a part of the other two cases (e.g. "I see you reaching out to me"). If you think about it for a minute, you'll realize that some distinct cases of the same pronoun are identical (e.g. the subjective and objective forms of "you").

For nouns, the subjective and objective cases are identical (e.g. "Kaity"). The possessive case, however, remains distinct (e.g. "Kaity's).

Interestingly, Old English used to have five cases: nominative, accusative, dative, genitive, and instrumental; as well, not only pronouns and common nouns, but also adjectives were declined. The instrumental case refers to the means by which the action of the sentence is performed. If Latin had had an instrumental case, "with burning truth" would probably have used it (but not "until the fated day", despite the fact that both use the ablative case in Latin). Interestingly, Old English lacked an ablative case; presumably the reason for this is that it relied on propositions to fill this role, as does modern English.

And for a few tangentially related bonus topics. I looked it up today, and vizzini (who is actually my boss) is right: proper nouns are declined in Latin. Also, I just had a question pop into my head: if we're evolving from simple to complex, why are languages evolving in the exact opposite way - English, Greek, etc.?

& Linguistics - Case - Latin

Today I'm going to go into a bit of a different topic - linguistics. Why? Because I feel like it. Specifically, I'm going to talk about case *ahem*

Case refers to alterations ("declension") of nouns and possibly adjectives, based not on what the nouns/adjectives refer to (though they usually do that, too), but in what manner they are used in the sentence in which they appear (phrased differently, what grammatical role they play).

The stereotypical declined language is Latin. All common (as opposed to proper) nouns and adjectives are declined - the exact word used depends on the case, in addition to other things like gender and number. Latin has six distinct cases: nominative, genitive, accusative, dative, ablative, and vocative. The nominative case refers to the subject of the sentence ("somnus non est" - "the sleep is no more"); the genitive case refers to the possessive ("invenite hortum veritatis" - "find the garden of truth"); the accusative case refers to the direct object ("urite mala mundi") "burn the evil of this world"); the dative case refers to the indirect object (e.g. "dona nobis pacem" - "give us peace" *); the ablative case being like the object of a preposition ("ardente veritate" - "with burning truth"); finally, the vocative case is used when speaking to someone ("exitate vos e somno, liberi fatali" - "arise from your sleep, fated children"). There's also a locative case, but that's rare, and sometimes omitted from dictionaries (and, more importantly, I'm not familiar with it).

If you were particularly alert, you might have noticed some things in those examples. Like the difference between "veritatis" and "veritate", "somnus" and "somno" (different cases of the same nouns); or the similarity between "ardente" and "veritate", "liberi" and "fatali" (paired adjectives and nouns in the same case). Or you might have even noticed in "ardente veritate" or "diebus fatalibus" ("until the fated day" - not shown previously), examples of the ablative case, that there is no proposition at all ("with" and "until", in English).

The use of a moderate set of cases in Latin (and the fact that nouns and adjectives are declined) make it a language that lends itself to poetry. Similar suffixes provide natural rhyming of similar thought patterns; the fact that sentence structure is determined by word form rather than word order allows free arranging of words in a sentence (within reason) while retaining meaning. The ablative case lends itself to poetic use, as well, but not in an immediately obvious manner. As the use of the ablative can imply the existence of a preposition without ever stating it (though there are also prepositions which may be explicitly used), it serves to reduce the precision of the language (as it's possible that more than one preposition would be appropriate in a given context), and lends itself to poetic metaphorical constructs.

* Sorry, there is no use of the dative case in Liberi Fatali, so I had to borrow one from Salva Nos

Day One

So, day one is officially over. Despite the fact that I have yet to be assigned any actual work, I managed to be halfway productive. During the second meeting for the three n00bs of us, something one of the guys said made me think he worked on Boost. So, after the meeting, I asked him if he did (he actually didn't, he just used it), and told him about LibQ (a "competing product"). He said I should send him a link, and he'd check it out.

10 or 15 minutes later, back at my computer, I decide to venture into the company's product. Double-click and... it fails to start with some vague error message. I call over Skywing, who spends half an hour or so debugging it and looking through the debug logs, to locate the cause. His first attempt to debug it used some debugger I'm not familiar with ("SD"). This resulted in the debugger crashing... repeatedly. Highly amused (it was pretty funny), Skywing ran over to the boss to tell him "Hey, Justin crashed SD!" The boss responded with something along the lines of "He what?!". "I'm not touching your LibQ!" followed closely, from another cubicle.

Despite the fact that he was joking (and it was actually pretty funny), LibQ ended up having the last laugh. Later in the day, I was randomly looking through the source code for their program (I figured that would be helpful when I, you know, actually have some work to do). After not too long, I found a piece of code that immediately set off red lights in my head. While it apparently works on Linux (that's what their server platform is), it will break on some versions of Unix (like OS X), should they ever decide to offer the program for other Unixes (which our boss, who's half coder, is actually working on, in whatever time he doesn't spend doing managerish stuff). So I filed my first bug report, in which I explained the problem, and referred them to the solution I used in LibQ (yes, I actually mentioned LibQ in the bug report).

Ding dong, the witch is dead!

Abu Musab al-Zarqawi, the al-Qaida leader in Iraq who waged a bloody campaign of
suicide bombings and beheadings of hostages, has been killed in a precision
airstrike, U.S. and Iraqi officials said Thursday. It was a long-sought victory
in the war in Iraq.

http://msnbc.msn.com/id/13195017/

Toto, I've a feeling we're not in California, anymore

And this is Q, reporting live from Kansas. Squid and I are here at a motel after a remarkably long day beginning with a 4 AM wakeup time, and including a 2400 mile flight taking 7 hours. Amusingly, Squid's carry-on bag set off the bomb detector, although that was resolved after a bit. I'm here for an internship at the company Skywing works for; Squid was just bored, and figured that out of state travel would be amusing.

Anyway, I'm too sleepy to think straight, and these phantom flight sensations are getting on my nerves. I think it's time for bed.

...and this laptop they're letting me borrow just started making an odd noise.

So I Was Bored and...

...looking through articles on lock-free data structures. Amusingly, one that looked interesting was by the author of Hoard - Quantifying the Performance of Garbage Collection vs. Explicit Memory Management. I didn't actually read the whole thing, but the conclusions were rather striking:

Comparing runtime, space consumption, and virtual memory footprints over a range of benchmarks, we show that the runtime performance of the best-performing garbage collector is competitive with explicit memory management when given enough memory. In particular, when garbage collection has five times as much memory as required, its runtime performance matches or slightly exceeds that of explicit memory management. However, garbage collection’s performance degrades substantially when it must use smaller heaps. With three times as much memory, it runs 17% slower on average, and with twice as much memory, it runs 70% slower. Garbage collection also is more susceptible to paging when physical memory is scarce. In such conditions, all of the garbage collectors we examine here suffer order-of-magnitude performance penalties relative to explicit memory management.

So, garbage collection doesn't sound so good for practical applications. Interestingly, this apparently debunks my belief that garbage collection was the optimal memory allocation strategy to use for embedded systems that are very tight on memory. Well, maybe, maybe not. I was thinking in terms of memory usage. Garbage collection allows blocks to be relocated in memory, allowing new allocations of arbitrary size to get around fragmentation problems (assuming there's enough free memory, period). But this report shows that doing so would come at a hefty performance cost, which may or may not be tolerable.

GNUPlot Update

It looks like, although even the most recent release version of GNUPlot behaves the same way I described, with regard to loading files, the development version in the CVS now uses exponential vector growth. Unfortunately, if you want to use that version, you'll have to download the source from CVS and compile it yourself, which may not be any easier than using the version with the vector flaw :P

Another Random Factoid

Yeah, that's more or less how the LFH works, with one key difference: the LFH is mostly lock-free. It's actually similar to but a bit simpler than the one I was going to implement. They also cheat a little: the list of partially filled reserve blocks is protected by a mutex. The allocator I was going to write didn't use a mutex there, because it used some tricky lock-free voodoo. I'm not sure whether or not the lock-free voodoo is worth the trouble - it will be slower when there's no contention, but faster when multiple threads are trying to access the same list. I'm not sure exactly how common an event that will be, though, since most allocations will come out of the current block, and the partial block list is only used when the current block gets full (essentially two threads would have to try to allocate a block from the same zone at the same time, when the current block is full).

Random Factoid

So, today I wondered what type of memory allocator OS X uses. So I looked around the XNU source code a bit, and found that it uses a zone allocator: there are 16 different memory pools (zones), each storing equal-sized blocks. Memory allocations are rounded up to a zone size, and a slot is popped off the corresponding zone like a stack. Each zone is protected by its own mutex. In other words, it's nearly identical to the allocator I want to implement, only it's semi-multi-processor friendly (due to the locks for each zone), as opposed to mine being completely lock-free (and thus full multi-processor friendly).

I suspect the Windows Low-Fragmentation Heap also functions like this, as well. Sometime I should reverse-engineer it to see if it's lock-free or has multiple locks (MSDN says it's multi-processor friendly, so it must at least have multiple zone locks).

On Vectors and Lists

So, a brief follow-up post to the one about the flaw in GNUPlot: data structures 101. Well, not all data structures, just vectors and lists. I wrote a simple implementation of a vector and a linked list, then benchmarked them while adding a large (the definition of "large" varies by structure) number of items.

Your basic list is very simple: each item is allocated from the heap, and does not require copying of any existing data items at any time. Insertions take O(1), and a string of insertions take O(N), as illustrated by this benchmark:



A vector is an array that gets resized whenever it gets full. When items are merely added to the end of an existing array, additions are O(1), and a series of additions are O(N). However, the process of resizing the array, which requires all existing items be copied, is O(N). This means that if you resize an array after a constant number of additions, additions to a vector will take O(N), and a string of additions will take O(N^2), as illustrated by this benchmark (the two series represent how much additional space was allocated each time the array was resized; 10 is the actual number GNUPlot uses when it reallocates its data array during file loading):



This is the WRONG way to use a vector. The correct way is to increase the size of the vector exponentially. In my benchmark I used a factor of 2 - every time the array became filled, its size was doubled. Since it's growing exponentially, the number of allocations that must be done (each taking O(N)) will be O(1/2^N); O(N * 1/2^N) = 0. Thus the time to reallocate the array is negligible, and the complexity is determined strictly by the time to add each new elements to the already allocated array: O(1) per element, and O(N) for a series of elements. This is shown in the following graph:

Regression: The Storm Strikes Back

Well, after messing with GNUPlot for most of the day, I believe I've obtained one of the results I sought: the regression equations for the different allocators. I cut off data points above 100,000 cycles based on looking at a couple plots; nearly all of the points were below 100,000 cycles, but some were significantly above that, and I wanted to minimize skewing due to outlier points. Nevertheless, there was a very large amount of variance in the data set (especially in the case of SMem), so you can expect a fair margin of imprecision. As well, I used the non-linear least-squares algorithm supplied in GNUPlot, which is somewhat susceptible to outlier points; at some point I may try recomputing the regression values using a robust regression method (something less susceptible to outlier points).

I suppose I should be getting used to the results of various experiments in this project surprising me, but I'm not; and this set of data came as one of the biggest surprises, after all the previously collected data. All regressions were performed using the general form m*(N^xp) + b, where m, xp, and b were solved for by the regression algorithm. I performed the graphs of the regression lines as log-log to maximize visibility of differences over the greatest range of points; you should not mistake these for linear graphs (for example, every single regression line was O(N^x), where x was less than 1, usually around 0.5; the log-log graphs, however, seem to suggest x is always greater than 1).

Most notably, SMem (Storm) takes a substantial lead at upper block sizes for allocations and frees (above 220 KB and 371 bytes, respectively); as well, it's not significantly worse than the other heaps at reallocations above about 5 KB. And no, the Windows heap doesn't really get down to negative cycles for allocations approaching 0 bytes; that's just an artifact of the regression calculation.

So, why did Storm perform so poorly in the bar charts? Well, that's relatively easy to offer an explanation for: it's probably because most of the allocations were smaller than Storm is optimal for. Though this does make me think that I should do some real-world tests, like replace all of SMem in Warcraft III with the other allocators, and see how long things like starting up, loading a map, and completing a map take (in other words, looking at clusters of operations that naturally occur together, which my benchmark is unable to take into consideration).

GNUPlot Fun

So, I'm trying to actually graph the full data sets. I believe I mentioned previously that I liked GNUPlot better than some of the others. However, it ended up being obscenely slow - it took 66 minutes to graph the realloc data set, which is about 60 megs large, and contains about 3.3 million data points (don't recall if I mentioned that). This absolutely confounded me. I couldn't conceive of any method that could possibly be that slow. I wrote a little program that used STL streams and extraction to see how long it would take to parse the file myself (keep in mind that STL streams are horribly slow): 2 minutes and 15 seconds.

So, I tried repeating the graph, telling it to graph every 20th data point, to see if the graph quality would be acceptable, while rendering in a reasonable amount of time (66 minutes / 20 = 3 minutes and 18 seconds, right?), using the handy stopwatch on my cell phone. This took 15 seconds. After a brief "OMGWTFBBQ" moment, the solution came to me: it was executing in exponential time. Gathering a few more times (1/17, 1/15, 1/12, 1/10, 1/8, and 1/5) confirmed this hypothesis: it was executing in O(N^2) time.



I can think of one "good" reason why it might be doing that: it's probably storing the data in a vector - a dynamically resizing array. Every time it gets resized, it has to copy the entire data set (which is almost 500 megs, by the end). This would produce the observed O(N^2) time. It also explains an odd behavior I observed while watching the GNUPlot execute in task manager. While loading the file, the memory usage increases over time. But the physical memory usage was ping-ponging all over the freakin place, varying at times by hundreds of megs (up and down) from second to second. I couldn't figure that one out, either; it was way too fast to be due to paging (my first thought). But it makes perfect sense if it's continually reallocating its buffer, copying the contents, and then freeing the old buffer.

*sigh* It seems like lately every program I've used I've needed to debug some catastrophic flaw in it. I have enough to do with debugging my own programs; you people need to leave me alone :P

More Thoughts on the Benchmark

So, in between games of Defense of the Ancients and the Warcraft III expansion campaign, I've been trying to figure out what causes those wildly deviating data points. One possibility is that it's context switches, either due to another thread getting the CPU (time-slicing), or to servicing of an interrupt. Skywing pointed out to me that only administrators may set threads to real-time priority (which disables time-slicing), and as a non-administrator, Windows will silently make real-time priority requests to highest priority (significantly higher than normal priority, so it will get virtually all of the CPU, but is still subject to time-slicing). And even real-time threads may be interrupted by a hardware interrupt *cough*

However, this doesn't explain the change in proportions between no cutoff and 50,000 cycle cutoff. The probability of an interrupt occurring while your thread is running is proportionate to how long your thread is running, meaning that, on average, the proportions should be the same, regardless of how long your thread runs for (this isn't strictly true for time-slicing, but I believe the alternate situation does not apply in this case, due to the extremely high priority of the benchmark thread, and the frequent "rest stops" the benchmark thread takes, to theoretically eliminate time-slicing).

Something that is interesting to note is that I just did a sum using a cutoff of 15,000. While this caused a moderate increase in speed, the proportions (ratios of one data series to another) remained almost identical to when a 50,000 cycle cutoff was used. This tells me that, regardless of whether the 50,000 cycle cutoff is too low, it's definitely not too high. The difference in times between the 50,000 and 15,000 sums may be due to valid allocations times that are higher than 15,000 cycles (maybe the large allocations? or the later operations?). Or, it could be due to short interrupt service routines getting executed (applying uniformly, as I predicted).

Memory Allocator Benchmarks - Take 2.1

Okay, I computed the sums again, this time using a cutoff of 50,000 cycles. I'm hoping that at that cutoff it will remove most of the outliers, while retaining calls to VirtualAlloc/VirtualFree. The results (I'm including the previous graph here, again, for easy visual comparison with the new data):





Sweet mother of Kaity - that's more than a little bit different than the first time around. The Windows heap is 7x, 1.5x, and 3x as fast as it was before the cutoff. Other than that, the Hoard allocation speed is about 5x what is was, and SMem reallocation speed is about 3x what it was. All the other categories are no more than 10% different (faster) than what they were originally.

What this tells us is that some operations (the ones just listed) on some allocators have dramatically greater variance in operation time. Exactly which of these two versions is the more accurate, I couldn't really tell you. I'd tend to think the first one (the one including outlier points) would be the more representative of actual usage, although it's more susceptible to outlier points skewing the averages.

Memory Allocator Benchmarks - Take Two (Kinda)

So, I finally got tired of procrastinating instead of finding a program capable of plotting and performing regression analysis on my 33 million data points or so. Ideally, I'd do a three-dimensional plot and regression analysis of the data (operation order vs. operation size vs. operation time), but in the mean time I did a simple sum of the time for all operations of a given type.

Once again the data speak for themselves, and again they surprised me. Hoard seems like a fairly well rounded choice, though the Windows low-fragmentation heap absolutely owned the allocation benchmark. SMem is, indeed, almost twice as fast as HeapFree, but gets its ass handed to it in the reallocation benchmark.

I'm not sure why SMemReAlloc does so badly. It's possible that it has a larger proportion of outlying data points (points in the hundreds of thousands or millions of cycles) than the others, which could severely skew the results, as this is a sum function. I may try doing the same process using some data point cutoff, and see how that affects the results; though I'm not sure what a fair cutoff point would be.

Oh, and for reference, from what I've heard, the Windows low-fragmentation heap is very similar to the algorithm I was going to implement for LibQ (the lock-free one).

Any-User Program Installation - Part 1

First of all, we want to create a group for users that will have installation privileges. This is so that you can, on a computer with multiple users (such as a business computer), you can only allow certain users to install programs.

This is done through the Computer Management console (at least in Windows XP), and requires administrator access. Computer Management is located under Administrative Tools, in the Control Panel. If you're not running as an administrator account, you can right click on Computer Management, and click Run as... to run the program as administrator (this is relatively convenient, as it allows you to run programs that require administrator access without changing users).



Go to the group list, right click on the list of users, and add a group called Program Installers. Add whoever should be there to the list.



That was trivial. In fact, all of these steps are going to be. I just decided to break them up into separate posts so that if I get lazy and don't feel like finishing the whole series today, I can at least have something to show for it :P

Howto: Installing Programs with Any User

I never did get around to the series I was planning to write about the Windows and Unix data/code models, and how to properly deal with this (which would make your program work for limited users). But after a brief "debate" (if you can call it that) on Slashdot, I had a whim to explain how to allow limited users to install programs on Windows, without having to use runas to access the administrator account (and done in a relatively safe, multi-user friendly way). You will, however, need administrator access to configure Windows to allow this.

Now, before I say anything more, let me point out that this is only intended to work on programs that are multi-user friendly (that is, they don't assume they can write to their Program Files folder whenever they please). Maybe I'll do a post afterwards about how to deal with those types of programs.

Right now I'm thinking this post series will have the following parts (each one should be pretty brief, as none of them are particularly difficult:
1. Creating a user group for users that can install programs
2. Allowing programs run by users to add to the Program Files folder, start menu, and shared desktop (while not creating a gaping security hole on multi-user systems)
3. Allowing programs run by users to add to the registry (same criteria)
4. (maybe) Having the system take ownership of programs after they're installed (so that one user can't uninstall something that is used by multiple users)

Now, note that, while I have a general idea of how to accomplish this, I've not tried this before; so this will be a learning experience for all of us. We'll deal with complications as they arise (I can already think of one that might come up...).

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

Okay, Enough of That

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

**** 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.

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.

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.

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

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.

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.

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.

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.

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.

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

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?

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...

& 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.

& 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*

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

& 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.

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.

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.

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.

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].