You are viewing paulmck

Tired of ads? Upgrade to paid account and never see ads again!

(no subject)

I skimmed Martin Rinard's paper and it's interesting stuff but a few key issues seemed to be missing.

The paper only describes inserting data structure pieces and does not describe removing them. So of course it doesn't crash despite lacking synchronization; you can't hit a "use-after-free" bug if there is no "free". I suspect there is some form of removal and freeing of the data structures at some point but it wasn't covered.

This is also important because if you accidentally lose track of inserted structures you have a memory leak whether you "crash" or not. Given the large number of bodies involved in these problems that leak could be substantial. If you *don't* lose track of these structures then perhaps we ought to say we're further amortizing the synchronization cost of some other structure rather than using synchronization-free algorithms?

The paper seems to be predicated on the Intel architecture memory consistency model. Does it work on architectures without that consistency model? My guess is it does not work on weaker consistency models but I didn't see a discussion of the consequences of other consistency models in the paper. "Link at end" is basically a pretty old (but good!) technique with only the final locking/synchronization around the pointer write omitted. My guess is this synchronization-free technique is less helpful with those other memory models.

Finally, the uniform distribution n-body problem described could very easily be concealing significant sources of error. What happens to accuracy when the masses are non-uniformly distributed? When the positions are non-uniformly distributed? For example, suppose you want to simulate dust accretion around a young star and the data structure accidentally omits the star. I'd expect you'd see some rather serious error despite the fact that 99% of the bodies were not omitted from the Barnes-Hut tree. Of course you could then model the star as many small(-ish) masses at potentially much greater computational cost. That might be an overhead worth analyzing since it could reduce the advantages of the synchronization free approach.

Comment Form

No HTML allowed in subject


Notice! This user has turned on the option that logs your IP address when posting. 

(will be screened)