VM crashes and more...

When I tried to rerun the last experiment again with the more accurate measurement method yesterday, the test did not finish. Some investigation pointed out that the java VM was crashing for some reason (link to dump). I have a weak suspicion that this crash is in some way caused by a bug in the subprocess python module. I think it may be doing strange things buffering input causing the jvm to write to some illegal part of memory or something like that.

To remedy this, I once again changed the script to send its stdout to file instead of PIPE, which reintroduced the "cutting off the output" bug I encoutered earlier. I tried a lot of different things to solve this problem, like changing the subprocess.call to subprocess.Popen, changing shell=True to shell=False, etc. None of this had any effect. I'm currently running again with a simple System.out.flush() after the print command in java code (I hope this flush is propagated from the java program to ant to maven to python). If that doesn't work, my backup solution is to send the timing output on stderr, which should be a pretty much empty stream and shouldn't have the same problems.

Ladder Queue work

Yesterday I also fixed the creation of a new rung from bottom. After this, my simulation-like test succeeded completely. Today I'm running something of a torture-test on the ladderQ, threating it like an ordinary queue (in something that's definitely not a discrete event simulation). I'm just inserting a large amount of completely randomly distributed [0-10000] events, removing a random amount of them, adding another large amount and repeating that for a few hundred times. The ladder queue will not perform well (in a time optimal manner) in a test like this, but it should be able to handle the test none the less.

This exposed another bug in the pseudo code, and one I definitely did not see in advance. When inserting a new element that's smaller than the start of the lowest rung, it should be inserted into bottom. To prevent degradation to a linked list, a check is made to see if bottom isn't too full when inserting that element, and if it is, bottom is moved to a newly created rung. The code for this goes like this (verbatim):

create_new_rung(NBot)
transfer bottom to it
bucket_k = <formula>
insert into tail of rung NRung, bucket_k
<increase number of event in that bucket>

There's a number of problems with this code: first of all, create_new_rung creates a new rung from an existing rung, while there is no guarantee that at that time a single rung exists. Furthermore, it simply does not handle the creation of a new rung from bottom correctly! Rstart and Rcur for the new rung should obviously be adjusted to the values in bottom, but they are not. The instruction insert into tail of rung NRung, bucket_k is also very much incorrect, seeing as how there is no guarantee that that event will even fit in that rung, seeing as how the rung was made before adding the new event. I'll handle this by replacing the insert into tail of rung NRung, bucket_k with a recursive call to offer() of the new event.