2

I have .hgt file which contains (1201x1201) 16-bit integers. I store this file in quadtree with max level 5. In leaf on level 5 i have ArrayList of Points: 

public class Point {
    short x,y,v;
}

x,y - coordination, v - elevation.

Everything work OK but it needs too much memory because im creating 1201x1201= cca 1.44M of objects. Im working on mobile application(Android) so this is problem because it takes more then 20 seconds to insert all Points and it "eats" all memory. Is there way how to decrease this ?

Heap Size: 49.258 MB

Allocated: 44.733 MB

data object: (Count:1 477 454),(Total Size:34.081 MB)

hgt file format

Community
  • 1
  • 1
Bowerick Wowbagger
  • 67
  • 5

1 Answers1

1

I'm not a JVM expert but last time I checked a Java object has 8-bytes (64-bits) of metadata that likewise seemed to require 64-bit alignment. That might be different on a 32-bit Android device, but based on what I found, your Point objects would require 16 bytes rather than 6, like so:

public class Point {
    // 8 byte metadata

    // 6 bytes of data.
    short x,y,v;

    // 2 bytes of padding for alignment of metadata.
}

... something to this effect. So that's ~2.67 times more memory use than should be optimally needed for 3 16-bit shorts. So one solution to reduce the memory for the points to less than half as well as improve locality of reference is just store everything in one or more giant short arrays, like:

short xyz[num_points * 3];

That would require very, very, very close to the optimal amount of memory (just the slightest bit of overhead, absolutely trivial in this case, to store some metadata for the array like its length).

That said, assuming Point was 16 bytes, that only explains about half of your explosive memory use (~23 megabytes for the points). The other is most likely your quad-tree nodes themselves. Still, you could reduce that down from 23 megabytes to ~8.6 megabytes if that's the case using the technique above.

For the rest of the memory use, my number one suggestion is to avoid storing a separate ArrayList for every single leaf node. You can just store, say, an index to the first point in a big array list (just one for the entire tree) and maybe one more integer for the number of elements stored in that leaf. This is a C-ish pseudocode example but you should be able to get your quadtree nodes to at least something like this:

struct QuadTreeNode
{
     // Stores AABB.
     float x1, x2, y1, y2;

     // Stores first child or -1 if empty.     
     int first_child;

     // Stores first element or -1 if this is not a leaf.
     int first_element;
};

struct QuadTree
{
     // Stores all the nodes in the quad tree. The 4
     // children of a node are stored contiguously.
     QuadTreeNode nodes[];

     // Stores all the elements in the quad tree. The
     // elements at the leaves are stored contiguously.
     Element elements[];
};

This isn't even really compact, but it's reasonably compact.

  • I also did a comprehensive write-up on how to tune quadtrees which covers the leaf and branch node reps: https://stackoverflow.com/a/48330314/4842163 –  Jan 22 '18 at 07:46