Search This Blog

Saturday, April 29, 2006

Updated

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

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

Thursday, April 27, 2006

& Wii

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

& Immunology Fun

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

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

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

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

Sunday, April 16, 2006

3, 2, 1, Contact!

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

Saturday, April 15, 2006

Today's Status

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

Flunked!

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

Friday, April 14, 2006

Caveat

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

OWNED

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

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

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

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

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

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

address
Yours Sincerely,
Aminu Ali Hassan.

Thursday, April 13, 2006

Sucks to Be Them

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

What Is It Good For?

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

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

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

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

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

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

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

Status Report

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

Happy, happy nights ahead!

Wednesday, April 12, 2006

Perfect Nerd Evolution

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

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

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

Monday, April 10, 2006

Why the AVI?

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

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

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

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

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

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

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

Forgot to Mention

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

& More Trophies

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

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

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

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

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

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

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

Saturday, April 08, 2006

& Trophies

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


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


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


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


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

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

Wednesday, April 05, 2006

& Stress

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

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

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

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

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

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

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

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

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

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

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

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