Re: Custom Data Structure vs. Primitive Array objects
sangwoo.im@gmail.com wrote:
Hi,
In last semester, I wrote a program for algorithm analysis class. It
was critical to make the program to run as fast as possible. My first
approach was making custom classes that can represent the required data
model for the given problem. But, the program ran extremely slow with
a large data set. I suffered from that performance problem and I
decided to rewrite the program with only primitive data classes that
provided in Java for default. obviously, there was no change in
programming logics or algorithms. It began to ran comparatively faster
than before. (It was amazingly reduced the running time.) This was a
weird observation for me because the custom data structure (class) that
I wrote before was just a data container with few methods for data
field accessors (getters/setters); there was no intensive computation
in the class. I'm just reasoning the observation by a guess. "Java
might handling custom objects slow due to the garbage collector
mechanism and maintaining the objects (retain counter, etc)." But, this
is just a guess. I have no clear reason to explain what I observed.
Would this happen in other programming language/environment, too?
Thanks for any comments
Sangwoo
In general, data organization can be key to practical algorithm
performance. At a minimum, it can affect the constant multiplier. In
some cases, it can even change the time or space complexity. For
example, in Java indexed access to element n of an N element list is
O(1) if it is an array or ArrayList, but O(N) for a LinkedList.
Changes in data organization can have dramatic effects on cache hit
rates. Most algorithms will not achieve acceptable speed if more than a
small fraction of loads and stores go to memory.
Theoretical algorithm analysis usually starts by ignoring cache issues,
because there is a finite upper bound on the ratio between performance
with and without caching. Cache hit/miss cannot affect the computational
complexity.
Your array and primitive version may have grouped together in memory the
data needed in the inner loops of the algorithm, in the order in which
it was needed.
Patricia