Today, I fixed a ton of bugs in Inventor IDE and added some simple-but-useful functionality I’d been putting off for a long time. It occurred to me earlier today that for almost all of these bugs, I’m probably the only one who’s ever encountered them, and some of them, even I never encountered them; they’re fixed without ever being experienced. I thought I’d share some of these bugs with you to give an idea of what I’ve been up to and what sort of bugs I encounter in Inventor IDE.
Bug #1: Huge JComboBox
This is one of those bugs that I can’t actually fix, but I managed to find a workaround after a whole lot of banging my head against the wall. There’s at least one bug in Java’s implementation of JComboBox that uses the Windows look-and-feel. It may have been fixed in Java 1.6 or later, but I have to build with Java 1.5 or nothing will run when somebody tries to run it with Java 1.5, even though I’m not using any Java 1.6 features.
The bug: suddenly and irregularly, the size of a JComboBox will become larger than 16384 x 16384. When Java tries to create a buffer into which to paint the JComboBox, it runs out of memory, because 16384 x 16384 x 4 bytes per pixel = 1GB.
It took a few hours to figure this out, because the stack trace for the OutOfMemoryError doesn’t contain any of my code (since I hadn’t overridden JComboBox.paintComponent()) and the bug rarely occurs. The way I eventually figured it out was that I put a breakpoint at one of the low levels in the stack trace, ran the code until I got a debugger trace that looked similar, and looked back at the object up the chain at the last pair of paint()/paintChildren() calls, and it turned out to be an ObservedStringComboBox (one of my classes). It wasn’t for a few minutes that I realized the size was so huge, and I discovered that getPreferredSize() and getMinimumSize() return similarly huge sizes too, so I traced into them. After an hour of crawling through the mess that is Java’s Swing, I found that it was probably that some object was giving a dummy value to indicate that it didn’t really know how large something was supposed to be.
The solution: I’ve overridden JComponent.paintComponent() in both classes I have that extend JComboBox, and they check whether the width or height is over 16384, in which case, they do a rough estimation of the size based on the string widths of their options. Then, they call setSize(), setMinimumSize(), setPreferredSize(), and setMaximumSize(), just to make sure, before calling the original paintComponent(). It successfully picked up the error when it occurred, and set the JComboBox to a reasonable size that didn’t look out of place.
Bug #2: Where’s the caret?
This bug has been around for quite some time, and although I was stumped on a good way to solve it (partly due to the next bug), it’s solution was a one-character change.
The bug:
The caret is currently at the beginning of the first “SegmentDescriptor”, but it’s impossible to see.
The border of the LineFields blocks out the one pixel-width of the caret that would be visible if it had no border.
The solution:
The exact same thing, but everything in a LineField is drawn 2 pixels to the right
This was literally solved by changing the insets from (0,0,0,0) to (0,2,0,0). Now the full caret is visible. (It didn’t look as good with just one pixel-width showing, so I have both pixels showing.)
Bug #3: The layout war
I hate layout issues; Java seems to have a neverending supply of them, which is why I removed LayoutManagers from a vast majority of the components that need good layout. There were a few major layout bugs that I still had though, and the most ridiculous-looking was to do with the layout of my ObservedStringTables (shown above correctly, but I’ll use a new example).
The bug: the ObservedStringTable should control the layout of the LineFields it contains, since they should be kept looking tabular, but many LineFields elsewhere are supposed to resize automatically to fit the current size of their text, so that behaviour was built into LineField.
An enumeration isn’t supposed to look this bad (btw, here, it auto-increments by “sizeof SegmentDescriptor” if no value specified)
The solution: it’s not a great solution, but by the time it’s lack of greatness would matter, it’ll have changed or need changing for other reasons already. I just have LineField check whether it’s in an ObservedStringTable, and if it is, it doesn’t change its own size.
Finally, it looks like a table
In case you’re wondering, yes, the caret is now not visible if it’s at the end of the Increment field. I’ll fix it now, ’cause I’ll forget something small like that… there we go; insets are now (0,2,0,2). 🙂
Bug #4: When the impossible is possible
Moving away from UI-related bugs, this bug was technically fixed today, though only because today started at midnight, not when I got up (11:30 AM). A few days ago, I added support for compiling inline functions that have only text-replacement parameters (i.e. macros minus support for elaborate macro stuff). That way, I can use it for having debug output functions in Own OS that don’t get called at all if “TEXT_TESTING_MODE” is false. However, fairly often when compiling, though unpredictably, there’d be an ArrayIndexOutOfBoundsException when adding a reference to a line or when adding an error to a line.
It’s fairly common to add errors to lines during compilation, since the error detection doesn’t check for everything before compile-time, but the only code that would be adding references to lines would be the code for inline function compiling. When I encounter a call to an inline function, I copy the function, replace the parameter references in the code with their given values, and remove the parameters. Then I compile it as a regular function, just in the middle of another function. The weird thing about this error is that upon adding a check to make sure that the array was large enough (which was even redundant, because the line before had been a call to ensureRefCapacity(), which expands the reference array if needed), it still had the same array index exception. The only way I could think of that this could happen is if multiple threads were messing around with the same line at the same time, but the odds of that were pretty low, considering I’d explicitly designed the compilation not to modify anything concurrently.
The bug: when a parameter is removed from a function that is in global scope, things observing the global scope get notified about it. A temporary copy of an inline function shouldn’t really be notifying the global scope about its parameters being removed, and updating code based on a notification is probably not something that should occur while compiling. Sure enough, functions didn’t like getting told that a temporary function they can’t actually access has lost a parameter.
The solution: this is one bug where I haven’t actually determined exactly how/why it was occurring, but the stack traces and stepping through debugging clearly showed that the error was only occurring when a temporary function was broadcasting to everybody that it had lost a parameter, which it shouldn’t be doing. I just stopped temporary functions from notifying the global scope of anything. It’s usually not advisable to fix something without fully understanding it, but often, such a restriction would mean that few bugs would get fixed. For now, I’m okay with this lack of understanding, because I’ll need to re-investigate and adjust this type of thing when I add support for function overloading when I add support for C, and until then, it’s unlikely that any oversight here will rear its head again.
Yesterday’s Bug: The complete round-off problem
So this wasn’t from today, but it’s a cool quirk of floating-point calculation with which programmers should familiarize themselves. Suppose that you have an array of floats (4-byte real numbers) that’s 2 billion elements long, and every single element contains the value 1. If you simply go through the array and sum up the values of the elements, what is the final sum?
You might guess that it’s 2 billion plus or minus some relatively small amount of error, but in fact, the sum is exactly 8,388,608. This is the case whether you have 10 million elements, 2 billion elements, or 1 trillion elements. The answer is still 8,388,608. Why?
floats have 23 bits of mantissa, and once they get to the value 8,388,608 (i.e. 1.0000…0×2^23), adding the value 1 would make it 8,388,609, but this can’t be represented exactly in floating point, so it gets rounded down (following the round even rule), back to 8,388,608. This happens for every single 1 that is added after that too. In general, when adding many values that are all positive (or all negative) of similar magnitude, the final sum will be around 8,388,608 times the average value.
This is exactly what I found in a piece of code I had changed to use floats instead of doubles at work (at D-Wave). It was trying to add 14,400,000 elements with roughly the value 1, and it gave 8,388,608 every time. Instead of reading the sum, I was actually reading the average, 0.582542 instead of about 1.0, so it wasn’t immediately apparent why it was wrong. I realized that this was the error when I ran it for 144,000,000 elements and got 0.058254, which is 10 times less for 10 times as many elements, meaning that the sum hadn’t changed. That brings up the question, how do you add up the elements in an array to avoid this?
The solution: Well, the way I fixed it at work was to just change it back to using a double (8-byte real number) to accumulate the values. That doesn’t encounter the complete round-off problem until 2^52 additions; it can still result in bad round-off error before then, but it shouldn’t be an issue for the piece of code we were doing this in. Is there a way that works for any number of additions?
One way that works in O(logn) extra space (or inline if you can destroy the data), while still being in O(n) time, is that you break it up by adding every pair, then adding every pair of those, then adding every pair of those, etc. The way that can be done in O(logn) space is that you keep a value for every level, all starting at zero, and when you’re done a level, you add the value to the next level up. If that was the end of the next level up, it goes up more, else you go back to the next at the bottom. This is equivalent to splitting it up recursively (using O(logn) stack space), only without the disadvantages of recursion. It also has the advantage that it could be done with data coming in over time. Note that there’s still the issue of round-off from adding positive and negative numbers that sum to near zero, but there’s not much that can be done about that.
Edit: Here’s code for this approach (untested):
float sum(const float*const array,const size_t size) {
// Assuming there is a function to compute the ceiling of log_2 of size
// The -1 is because the lowest level (pairs) gets added immediately instead of waiting
const size_t logSize = ceilLog2(size)-1;
float accumulators[logSize] = {0};
bool isSecondHalf[logSize] = {0};
float sum;
for (size_t i=0; i<size-1; i+=2) {
// Add together a pair of elements
sum = array[i];
sum += array[i+1];
size_t level = 0;
// Go up the tree until reaching the end
// or a place where it's the first half
while (isSecondHalf[level]) {
isSecondHalf[level] = 0;
accumulators[level] = 0;
sum += accumulators[level+1]
++level;
// Handle case of size being an exact power of two
if (level==logSize) {
return sum;
}
}
// Save the sum at the highest level reached
accumulators[level] = sum;
// Now on the second half of that level
isSecondHalf[level] = 1;
}
// Make sure to get the last element if there were an odd number of elements
sum = (size&1) ? array[size-1] : 0;
// Add up all values left in accumulators (order matters)
for (size_t level=0; level<logSize-1; ++level) {
sum += accumulators[level];
}
return sum;
}
Posted in Inventor IDE, Programming
(the harmonic series) divergesas n approaches infinity, and more recently, that it scales as 
. However, 
converges, along with any other positive function 
being summed. For a while I had assumed that any function 
would converge, but I learned in my second calculus course at Carleton that 
also diverges.
. Using a similar approach, one can show that 
. Doing this again can show that 
, and a pattern emerges allowing each one to be expressed in terms of the previous.
is just to prevent any of the logarithms from going to zero, so assume 
. If any one of the logarithmic factors in the sum has a power greater than one, the series converges, but with them all equal to or less than one, the series still diverges. In effect, the scaling can get arbitrarily close to 
, so this appears to be the very brink of divergence. Some may argue that having a finite k makes it insufficient, since there are theoretically slower-growing functions, but that’s really splitting hairs.
ndickson's blog 