Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Sun, Sep 20, 2009 at 4:40 AM, Ľubomír Varga lu...@plaintext.sk wrote: AFAIK this is possible right now. Just use PostGis database of world, connect GeoServer like renderer / transformer to WMS / WFS / WSC and add WMS layer to JOSM. So in JOSM you could view whole world from PostGis (postgres) database. It is of course possible to use it *now* if all you want to use it as is a WMS. But the suggestion was to use it as the native data storage format. ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Sat, Sep 19, 2009 at 6:15 PM, Dave Hansen d...@sr71.net wrote: On Sat, 2009-09-19 at 08:36 -0400, Greg Troxel wrote: I have wondered about hooking up postgis to josm as a working data storage format, so you can use spatial queries and indexes. That's got a lot of downsides, but I wonder about it being an optional setup for those working with big datasets. It's an interesting idea, but I don't know enough about postgis to give you an intelligent answer. PostGIS can be used as a backend for other GIS programs such as ArcGIS. So I think any potential troubles in this regard would have more to do with what sort of requirements JOSM makes of its data model than PostGIS limitations. Such an integration could bring some very neat features. Like being able to view the whole planet in JOSM with PostGIS on the backend with JOSM only requesting the data that it needed to display at any one time. With other operations such as search being (optionally) global. ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
AFAIK this is possible right now. Just use PostGis database of world, connect GeoServer like renderer / transformer to WMS / WFS / WSC and add WMS layer to JOSM. So in JOSM you could view whole world from PostGis (postgres) database. One problem is imho sld style for rendering which I doesnt found and it probably have to be writen manually. PS: searching thru WFS could be probably done by cql query. But Iam not sure about this. On Saturday 19 September 2009 21:36:04 Ævar Arnfjörð Bjarmason wrote: On Sat, Sep 19, 2009 at 6:15 PM, Dave Hansen d...@sr71.net wrote: On Sat, 2009-09-19 at 08:36 -0400, Greg Troxel wrote: I have wondered about hooking up postgis to josm as a working data storage format, so you can use spatial queries and indexes. That's got a lot of downsides, but I wonder about it being an optional setup for those working with big datasets. It's an interesting idea, but I don't know enough about postgis to give you an intelligent answer. PostGIS can be used as a backend for other GIS programs such as ArcGIS. So I think any potential troubles in this regard would have more to do with what sort of requirements JOSM makes of its data model than PostGIS limitations. Such an integration could bring some very neat features. Like being able to view the whole planet in JOSM with PostGIS on the backend with JOSM only requesting the data that it needed to display at any one time. With other operations such as search being (optionally) global. ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev -- Odborník na všetko je zlý odborník. Ja sa snažím byť výnimkou potvrdzujúcou pravidlo. ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
I ran josm with your patch. Here are some initial general observations which do not include any analysis of the algorithm itself. It seems the QuadBuckets class is referenced only through the CollectionNode interface, and none of the features (i.e. fast searching within a bbox) are actually used? Rather than adding dead code (presumably with a view to enabling it later), an easier path into the trunk might be to first refactor josm to use a SpatialIndex interface that initially is backed by a List/Collection (i.e. low risk and no change to current performance), and adding working indexes later (initially via plugins for testing). Another observation: It looks like QuadBuckets only works with actual Lat/Longs (i.e. no numbers above 360). It would be nice to handle arbitrary coordinates - two use cases that come to mind are: 1. index screen coordinates (e.g. so that a highlight can follow the nearest object to the cursor and indicate what would be selected if the mouse was clicked). 2. index projected coordinates Finally, a spatial index implementation should be generic enough to be used in multiple places in the code (e.g. an index of way segments, or whatever), so implementing CollectionNode is too specialised. Aled ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Wed, 2009-09-16 at 10:01 +0100, A Morris wrote: I ran josm with your patch. Here are some initial general observations which do not include any analysis of the algorithm itself. It seems the QuadBuckets class is referenced only through the CollectionNode interface, and none of the features (i.e. fast searching within a bbox) are actually used? Yes, you are correct. I actually tested it inside the validator plugin's UnconnectedWays test. It was developed wholly outside of the JOSM codebase and crammed back in later, actually. *Not* using its search features inside of JOSM is actually a plus at this point. Since it can't notice changes in node coordinates, it actually breaks if a node moves. Rather than adding dead code (presumably with a view to enabling it later), an easier path into the trunk might be to first refactor josm to use a SpatialIndex interface that initially is backed by a List/Collection (i.e. low risk and no change to current performance), and adding working indexes later (initially via plugins for testing). It's actually not dead code. It isn't seeing wide use, but I have at least one user. :) Another observation: It looks like QuadBuckets only works with actual Lat/Longs (i.e. no numbers above 360). It would be nice to handle arbitrary coordinates - two use cases that come to mind are: 1. index screen coordinates (e.g. so that a highlight can follow the nearest object to the cursor and indicate what would be selected if the mouse was clicked). 2. index projected coordinates I agree with you in general. If you compare my code to the ruby quad tiling code that I copied from initially, you'll notice that I took great care to make the code more generic. Also, in moving from 32 to 48 bits of precision, I made the code much more flexible along the way. Finally, a spatial index implementation should be generic enough to be used in multiple places in the code (e.g. an index of way segments, or whatever), so implementing CollectionNode is too specialised. Heh. I did this in the last 4 seconds before I posted the patch, just so it would do *something*. Personally, I subscribe to the release early, release often, open source philosophy. This was an early release. I'd much rather have it integrated into JOSM now so that I can spend less time on cramming the patch back into the source every few weeks and spend more time on making it more generic, for instance. At this point, it doesn't *hurt* anything in JOSM. I'm not going anywhere and I'll be around to fix it up. As soon as we have proper OsmPrimitive change notifiers, I'll hook this code into it and we can start using it more widely. -- Dave ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Sat, 2009-09-12 at 23:52 +0200, Petr Nejedlý wrote:
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
Really?
Yep, and I made a number of runs. It was on the order of 5% or so.
But, I'm sure it depends heavily on how you populate the tree and how
close all of the data structures are in memory. It also depends on how
sparse your data is in the tree on average and the size of the leaf
buckets.
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:
ArrayList.size() {
return size;
}
LinkedList.size() {
return size;
}
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).
Yes, it should be nicer to caches. But, java is weird. It gets laid
out in all kinds of wacky-ass ways and it's backwards from what I expect
sometimes.
Notice that I didn't say that calling .size() was slower on ArrayList
than LinkedList. I said it was a part of the *iterator*. LinkedList
iterators don't have to consult .size, they just know when they're at
the end because they see either the list head or null.
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 ;-))
Granted, what I did may just have been to switch to a list that doesn't
*call* size during iteration, but the overall performance did improve
for me. It could be for a large number of factors, though. I'm sure
that there's relatively poor locality of adjacent LinkedList elements,
but I just haven't seen it show up.
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).
Amen to that. I'm wasting a ton of cycles. It certainly has a *lot* of
room for extra optimization. There's a ton of coordinate comparing that
could probably just be done with the quad indexes themselves, and
there's plenty of calculation to be saved.
But, my approach so far has been to do what I found easiest to code. If
things start to make it slow, I optimize it. No need to optimize (and
complicate) things that aren't causing an appreciable impact.
I consider simple and fast to be way better than really really fast and
complicated. ;)
-- Dave
___
josm-dev mailing list
josm-dev@openstreetmap.org
http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
Hi Dave Any idea how you want this to look? I'm starting to code some primitive things, and it would be nice if I could get whatever I do merged eventually. AFAIK, nothing has been done so far. * Object updates are rare, and it is OK if the notification process is relatively slow * Rather than storing a list of all listeners that should be consulted on each object, store a (relatively) global list of listeners. Each listener would get all object updates for a particular type. That keeps us from having to store anything in *each* primitive. Currently, JOSM manages a list of data change listeners on *application* level. We'd need data change listeners per data set or per layer. Events should be emitted automatically, no call to fire... necessary by clients which update objects. Efficent batch processes are more and more important (see validator plugin, see upcoming changeset revert tools, see conflict resolution tasks), though, and it would be nice if data change event propagation could be used in two modes: immediate event propagation after an individual upate, event propagation after some kind of batch job has finished. I also want to have a ReverseLookup (node - ways) cache. I've had it sitting in the validator, but it's hard to keep it coherent and I end up throwing it away too often to make it useful. I recently hacked a basic revere lookup table for child/parent relationships (node - way, node - relation, way - relation, relation - relation), but it has to be build from a dataset on request, for instance before you start to fix 1000 duplicate nodes in validator. That's what the lookup table is currently used for (mainly in the new merge node action). Thinking about it, though... If we had ways in QuadBuckets, I probably wouldn't need the ReverseLookup cache. I'd just do a search for ways around a node and I'd just get the ways that are using the node back. Yes, but consider relation members too. That's where we often need reverse lookups. Regards Karl ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
Dave Hansen writes: So, I went and implemented it. I call it QuadBuckets, and it's basically an unbalanced 4-way radix tree structure. Well done, Dave! -- --my blog is athttp://blog.russnelson.com Crynwr supports open source software 521 Pleasant Valley Rd. | +1 315-323-1241 Potsdam, NY 13676-3213 | Sheepdog ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Saturday 12 September 2009, Dave Hansen wrote: I've been hacking on the JOSM validator plugin for a while. One of the repeating hard problems that comes up are doing the UnconnectedWays tests. You need to do searches for every segment in a way to see if there are any nearby nodes. This generally means that you do a number of searches on the same order as the number of nodes that you have. ... Dave, I realize this is quite a crude reply to such a detailed email. Did you investigate kd-trees at all? http://en.wikipedia.org/wiki/Kd_tree robert. ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Sat, 2009-09-12 at 17:58 +0100, Robert Scott wrote: On Saturday 12 September 2009, Dave Hansen wrote: I've been hacking on the JOSM validator plugin for a while. One of the repeating hard problems that comes up are doing the UnconnectedWays tests. You need to do searches for every segment in a way to see if there are any nearby nodes. This generally means that you do a number of searches on the same order as the number of nodes that you have. ... I realize this is quite a crude reply to such a detailed email. Did you investigate kd-trees at all? http://en.wikipedia.org/wiki/Kd_tree Nope. I did some searching to find multidimensional search algorithms before I started this, but none of them seemed too horribly nice. kd-trees do like quite nice. I do believe what I've implemented is relatively close to what they do, though. They have the advantage that they split in a single dimension at each level in the tree. QuadBuckets are hard-coded for 2 dimensions and just basically split into those two dimensions at once. But, I think there is a lot of similarity. It also looks like kd-trees are intelligent about the values at which they decide to split. This means that if you have a bunch of entries all bunched up into one end of a bucket and you split it, you'll always get them split in half. QuadBuckets will instead force a bunch more splits until the buckets are well-split. QuadBuckets are stupid about where the split: they only do it into geometric quarters of the original bucket. I basically chose the algorithm that I did since it modeled something else that I and other OSMers are familiar with. It's even possible that we could use the quadtile indexes in a way to make communication with the DB server faster, although I'm using slightly different calculations than it is as it stands now. If someone knows of any existing Java kd-tree implementations, I'd be happy to look into it and see if it could be applied here. I love nothing more than to throw my own code away. Seriously. ;) -- Dave ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Sat, Sep 12, 2009 at 5:11 PM, Dave Hansen d...@sr71.net wrote: If someone knows of any existing Java kd-tree implementations, I'd be happy to look into it and see if it could be applied here. I love nothing more than to throw my own code away. Seriously. ;) Google turned this up for kd-tree java: http://stackoverflow.com/questions/253767/kdtree-implementation-in-java ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Sat, 2009-09-12 at 17:25 +, Ævar Arnfjörð Bjarmason wrote: On Sat, Sep 12, 2009 at 5:11 PM, Dave Hansen d...@sr71.net wrote: If someone knows of any existing Java kd-tree implementations, I'd be happy to look into it and see if it could be applied here. I love nothing more than to throw my own code away. Seriously. ;) Google turned this up for kd-tree java: http://stackoverflow.com/questions/253767/kdtree-implementation-in-java One of those links is a 404, and the other looks like a C++ class that has a Java API. I'm not sure that'd be very easy to integrate into JOSM. Thanks for the links, though! -- Dave ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Sat, Sep 12, 2009 at 5:31 PM, Dave Hansen d...@sr71.net wrote: On Sat, 2009-09-12 at 17:25 +, Ęvar Arnfjörš Bjarmason wrote: On Sat, Sep 12, 2009 at 5:11 PM, Dave Hansen d...@sr71.net wrote: If someone knows of any existing Java kd-tree implementations, I'd be happy to look into it and see if it could be applied here. I love nothing more than to throw my own code away. Seriously. ;) Google turned this up for kd-tree java: http://stackoverflow.com/questions/253767/kdtree-implementation-in-java One of those links is a 404, and the other looks like a C++ class that has a Java API. I'm not sure that'd be very easy to integrate into JOSM. Thanks for the links, though! You can find that 404-ed class on Google Code: http://google.com/codesearch?q=KDTree.java ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
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. 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? Dave Hansen napsal(a): QuadBuckets also happen to implement CollectionNode. 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. You're right, though. This can't simply be dropped in for the node list and retain its searching abilities. -- Dave ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
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. This is the very motivation Jiri and myself have been working on replacing direct field access with accessors. Now we can start to work on features which will really improve JOSM, a spatial index for instance. -- Karl -Ursprüngliche Nachricht- Von: Dave Hansen [mailto:d...@sr71.net] Gesendet: Samstag, 12. September 2009 21:19 An: Petr Nejedlý Cc: karl.guggisb...@guggis.ch; 'Ævar Arnfjörð Bjarmason'; josm-dev@openstreetmap.org Betreff: Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM 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. 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? Dave Hansen napsal(a): QuadBuckets also happen to implement CollectionNode. 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. You're right, though. This can't simply be dropped in for the node list and retain its searching abilities. -- Dave ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
Re: [josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM
On Sat, 2009-09-12 at 21:36 +0200, Karl Guggisberg wrote: 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. This is the very motivation Jiri and myself have been working on replacing direct field access with accessors. Now we can start to work on features which will really improve JOSM, a spatial index for instance. Any idea how you want this to look? I'm starting to code some primitive things, and it would be nice if I could get whatever I do merged eventually. * Object updates are rare, and it is OK if the notification process is relatively slow * Rather than storing a list of all listeners that should be consulted on each object, store a (relatively) global list of listeners. Each listener would get all object updates for a particular type. That keeps us from having to store anything in *each* primitive. I also want to have a ReverseLookup (node - ways) cache. I've had it sitting in the validator, but it's hard to keep it coherent and I end up throwing it away too often to make it useful. Thinking about it, though... If we had ways in QuadBuckets, I probably wouldn't need the ReverseLookup cache. I'd just do a search for ways around a node and I'd just get the ways that are using the node back. -- Dave ___ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev
