Re: Optimization problem
tnorgd@gmail.com wrote:
Important part of the program are bulk operations, e.g. center of
mass, which is a simple arithmetic average of all points. The data
structure described above is very slow for that purpose. I have nested
loops iterating over thousands of objects. So far I got the following
solution:
Define "very slow." Did you actually measure your program and find that
the design overhead was the bottleneck in your code?
And somewhere else I have a global array: double[N][3], where N is the
number of points, known in advance. Each Point class actually has a
reference to a single row from this array. Then a method performing a
bulk operation on points take this array as an argument. Some
preliminary tests show that this is much faster, but I couldn't say
how much without rewriting the whole code...
My gut is telling me that the speed difference would amount to only a
few clock cycles under well-written, optimized, JIT-ed code; I think it
should come out to merely another memory indirection reference or three,
but I had no hand in writing a VM's JIT or optimization code, so I'm not
a reliable authority in the subject.
QUESTIONS:
- what do you think in general about the global array Nx3 idea?
I don't know how "global" this N of yours is. If it's truly global,
global enough to be a static variable on Point, then I think you could
garner much of your supposed speed improvements with some clever static
code in Point.
- I was told that memory paging is a very important factor when
efficiency is concerned (and that is one of my problems: my 10 000
objects have huge memory overhead). Do you think 300kB array of
doubles is small enough?
I'm sure everyone here was once told that Java is too slow to do
anything reasonable. The best thing I recommend is to try it and see
what works.
- I am worried that when I allocate my double[N][3] array, my
coordinates (of type double[3]) will be sparsely allocated in memory
and I don't earn anything.
The |new double[N][3]| expression would evaluate into multianewarray,
although the OpenJDK version of hotspot doesn't appear to pack that into
contiguous memory. Despite that, I think the entire allocation runs
without GC so the actual heap layout is most likely near-contiguous,
provided you have sufficient contiguous free space.
I think your fears of sparse allocation are overblown, but I'd recommend
looking at a heap map to double-check.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth