[josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
petr at nejedli.cz
Sat Sep 12 22:52:15 BST 2009
Dave Hansen napsal(a):
> On Sat, 2009-09-12 at 21:04 +0200, Petr Nejedlý wrote:
>> Dave Hansen napsal(a):
>> > Ooh, I forgot about josm-ng. That one looks very usable. If mine
>> > doesn't pan out, I'll certainly look at that one.
>> Well, the QTree in josm-ng is similar to yours in the way it distributes
>> the content, though I did pay quite some attention to memory usage
>> (hint: e.g. LinkedList is not the collection you'd like to use unless
>> you have specific reason to)
> For the leaf nodes you mean? I actually got better performance out of
> it than I did ArrayList. Honestly, I've been looking at performance a
> lot more than pure memory usage, so I bet you're right. But, when you
> have an absolute ton of ArrayLists around that you're iterating over a
> lot ArrayList.size() actually shows up in the profiles pretty high.
Well, guess what:
The size() call is probably the only thing where LinkedList matches
ArrayList speed wise. It has faster add/remove in the middle, but
everything else is slower. Even iteration (which has to follow two
pointers per entry in LinkedList) is slower than in ArrayList (which
follows just one and accesses an array linearly, being nice to caches).
So if ArrayList.size() shows up pretty high in the profiler, blame the
profiler (or the selected profiling method, or the interpretation of the
data, which is where most of the confusion usually came from ;-))
>> and support also 2d entities (node is
>> zero-d). The problem with importing it directly into josm is that it
>> uses (in -ng) the projected (and integer) coordinates. While it doesn't
>> care whether the coordinates are projected or not, it hugely benefit
>> from their signed integer nature.
> You just mean that they're cheaper to deal with than doubles/floats?
Partially, and also because I don't need to do all the math converting
coordinates to given bit pattern. Your quadTile (being long) has some
similarity to this, though you seem to be wasting precious cycles by
recomputing the whole quadTile at every level just to get 2 bits out of
it. (I would generally diverge from the quadTile by skipping the
expensive bit interleaving anyway).
>> Dave Hansen napsal(a):
>> > QuadBuckets also happen to implement Collection<Node>. So, we can
>> > just plug it in for Collection like in the DataSet class.
>> I have not looked at the josm codebase for a while, but as long as
>> Node has publicly mutable coordinates, you can't honestly do it.
>> If anything moves a node, it has no way to automatically jump into the
>> new bucket. And it makes no sense to try patching all the places which
>> can move a node (MoveCommand is not the only one).
> Just recently, Node/Way/Relation require access to be via accessor
> functions. That should help out quite a bit. The one thing that we do
> need is for a list of PrimitiveChangeListeners or something to call when
> primitives do change.
Great. Such an improvement can move josm miles forward when it comes to
dataset integrity and can even allow automatic undo queue management in
the long run!
All in all, please don't take my comments as a criticism. I'm glad that
somebody (all you folks actively working on josm) can get through with
such changes which I haven't had the patience to explain and implement
cooperatively and pursued the -ng instead.
More information about the josm-dev