Not especially, I'm afraid... The problem with saying "trust my judgement that k-d trees are no good" is that if you're not sharing the reasons, you're making it harder for us to know what else might be no good. Personally, I think your focus on O(1) better than O(log n) sounds potentially a bit misguided and might be closing you off from reasonable solutions.

The other thing that I'm unclear about here is that you say this takes 30 minutes "without searches" which sounds a little like you have a performance issue but you are optimizing something else that is not part of the performance problem. There are so many little ways to kill the performance of a good algorithm and a lot of performance is making your code work well with your hardware.

For example, if you can keep things in L3 cache and avoid invalidating it, you can see remarkable performance increases. It can be a much more significant factor than O(1) versus O(log N)

@JimmyJames What I mean is that even after spending time turning the code, using fast libraries (ex., fastutil, dsiutils) there's still a lot of math going on that takes time to run. I've been spending time playing around with object creation because the GC starts to cause problems after things have been running too long.

I wish it was just as simple as keeping things in L3 cache... but I don't have have 136 MB of L3 at my disposal. :D

GC, huh? Java?

Yeah, this is all written in Java.

L3 was really just an example. One thing you might want to consider is making your young generation really huge.

I'm running some metrics on the KDTree to share to satisfy everyone, but the KDTree is running much slower than the hashmap strategy.

The scenario where you create lots of objects that live long enough to get to the old generation and then get collected there is basically the worst case scenario.

With memory being so available now, I've had good results with things like 12GB of young and say 2GB tenured.

There's some weird stuff in the code as well to try and get around that - looking up where an entity is in the hashmap is basically a free operation - I'd have to hunt in YourKit for the method. That also gives us other occupietns of the same location for free.

I can do that with the computers in the lab, but my workstation only has 8GB.

In the lab we have stupid amounts of RAM though and they already know that the 10M runs will only take place there.

Using that setup we can GC something like 6GB in 0.1 seconds with no major GC cycles over months of up time.

I'd have to look at exact numbers but it's super fast

Most of my reading about KDTrees has been that 1) they are really hard to tune the implementation of and when you've got a lot of CRUD happening it get's even worse. The entities are uniformly distributed too, so no clumping which drives up the odds of the worse case O(n).

You can do a 6-1 split. If you can get the live set to fit in around 3GB.

Looks like 1M peaks at around 2GB, so 3GB might be workable

The young generation is split in half and you have eden too so it's wasteful on RAM but 64 bit arch makes it possible.

I'm thinking I'll be throwing a question over on SE about turning - will link it here when I do.

gotta run but I'll point you to my old thing I coded up. you might need a custom solution.

Sounds good, thanks!

I found it. It's 11 years old and I can't say it was thoroughly tested but if if you look at the getClosestPoints() method, you can probably make out the algorithm and fix what needs it. Since you are more concerned with write speed than read speed, you can tweak when things happen. Of the top of my head is that you can increase the max points in a cell i.e. minimize the number of cells.