111–120 of 124 posts
Implementing all-pairs similarity search on a few hundred million records. Naively approached, the complexity of this is O(N^2), so had to come up with novel ways to make it finish in a reasonable amount of time and with limited resources.
"Aha!" you say. "You're smashing the stack! Function b() is writing outside its stack frame."
But function b() was provably not doing that.
Function b() called msgrcv(), which has a very badly designed API. It takes a pointer to a structure, and a size parameter. The structure is supposed to be a type field (long), and then a buffer (array of char). The size parameter is supposed to be the size of the buffer, not the size of the structure. The original code that implemented this came from a contractor, and they made the very natural mistake of putting the size of the whole structure in the size field. This meant that an extra long was read from the message queue, and smashed the stack.
But that should mess up the stack from from function b(). How did it mess up a variable in function a()? Well, the compiler put that variable in a register, not on the stack. So when b() was called, it had to save off the registers it was going to use, so a()'s local variable wound up in b()'s stack frame.
It took me most of a month, off and on, to figure that out.
It had three CCD cameras with strip imagers that were combined into a single all-sky image every orbit.
I was given a FORTRAN codebase that dated back to the 70s (supporting functions) and was told to figure out the best way to pick the start and end of the orbit as far as image frames were concerned.
The pointing data was in satellite frame-of-reference quaternions [1], and the satellite orbited about the axis of the Sun-Earth line, approximately.
Approximately was the key. Since it wasn't at a perfect 90 degree angle, the CCD strips each crossed over the plane defined by the Sun-Earth line and the axis orthogonal to the Earth's orbit (I referred to it as "south") at an angle.
So, if you want to stitch together an image of the sky that looks continuous, but the orbit of the imager wobbles a bit, and different discontinuities show up every day, how do you do it?
The leading CCD could be entirely across the southern line when the other CCDs were just starting to cross it. This created a lot of problems with how you define a complete orbit that lacks discontinuities and makes intuitive sense so others can understand the code.
I decided to pick the point where the middle of the central camera crossed the plane as the frame of reference for the start/end point.
Ultimately, this project took me about three months, just to get used to the code base, the spatial coordinates and transformations needed to make sense of the data, and then to finally write the code.
The meaningful changes I made in the commit consisted of about three lines of code.
I found the commit message:
Fixed problem near seam of map where start and end of orbit meet. The orientation of camera 2 at the start of the orbit is now used to draw a reference great circle on the sky. Near this boundary pixels are tested individually to decide whether they are part of the current orbit and should be dropped in the skymap. Introduced torigin to keep track of the time origin for the lowres time map. This is added to the Fits header of the time map as keyword TORIGIN (used to be STIME). Times tfirstfrm and tlastfrm are assigned the time of the first and last frame, respectively, for which at least one pixel was dropped in the skymap. These are written into the main header of the skymap as keywords STIME and ETIME. Added extra extension to lowres maps containg nr of pixels contributing to each lowres bin
[1] https://en.wikipedia.org/wiki/Quaternions_and_spatial_rotati...
We started Friday after normal working hour by checking that the backup worked (it did) then proceeded to upgrade the server with a raid backplane and three new scsi disk, installed Windows NT, installed the backup software and started a restore while getting some takeaway.
The restore only took like 15 minutes - and to our horror we discovered that the previous IT admin had set it up to do an incremental backup on the same dat tape overwriting it every day!
Ok, no worry, we had not used the old disk, so we installed it and turned on the computer.... Nothing happened.... Strange, we removed the raid backplane, installed everything as it had been... Still nothing.
After 24+ hours working on the problem, including several hours talking to compaq support (best support ever!) we had to go home for some sleep. When I got back to the server room I fired up Norton Disk Editor and painfully figured out the MBR was all zeros on the disk, luckily the rest of the disk look like correct data!
Several hours later, just before sunday turned to monday I finally got an MBR written using NDE and NDD, booting the system and seeing everything was all right.
Monday we told the customer we had some problems and would do the upgrade another day (after we had taken multiple backups :)
Think about that the next time your code gets you down.
I was part of a team that designed and implemented a P2P UDP based video streaming protocol, that receives chunks of a stream simultaneously from up to hundreds of peers. It wasn't a "big problem" per se - I worked on seemingly harder problems before and since - but this one was really hard to get right, it was a very non deterministic beast that was extremely hard to test. I remember lots of times that I secretly fe…
Out of interest, did you use skiplists to reassemble the streams in order?
If you've already asked, one cool part of that technology is that the order of received packets is not important to assemble the stream. Basically every 1 second of video is reassembled without importance to the order of packets received. You need N packets to assemble a "data frame", IIRC pending incomplete data frames were stored in a simple hash table, but honestly it was so long ago I don't remember.
I was happy with this, until a friend challenged me to make it realtime. I managed to re-implement the same thing by using the built-in vector drawing (and as a bonus, this also gave anti-aliasing) and managed to get this down to 15ms.
The third version was using the 3D acceleration, and managed to get 100 lights to render in realtime. Was pretty proud of myself and I wrote an article about it, which was cited a few times by different people.
And yes, I know a lot of what I just typed will probably put real game programmers' teeth on edge.