[postgis-devel] Memory Leak (Two Senses)

Wed Jan 7 02:50:57 PST 2009

Paul Ramsey wrote:

> The second memory leak. The lwfree_pointarray function is defined in
> lwgeom_api, and it is directly below a comment block that says *this*:
> 
> /****************************************************************
>  * memory management
>  *
>  *  these only delete the memory associated
>  *  directly with the structure - NOT the stuff pointing into
>  *  the original de-serialized info
>  *
>  ****************************************************************/
> 
> Oh! That seems pretty clear. So by changing the function to fully
> clean up after itself, I'm contravening the documented intent.
> However, grep tells me the function is but lightly used in the code
> base, hardly at all, really.  Our second memory leak is historical, we
> have no idea why the intent was once this way.
> 
> Before I commit the changes to the lwfree_* set to make them finally,
> actually, do deep freeing, can anyone provide the historical context
> around the rules I seem to want to break?

Yes - if you do this it will break liblwgeom use within PostgreSQL :( 
Before I was ill over Christmas, I started looking at your complaint 
about manipulating MULTI-geoms in liblwgeom, and realised that the 
reason the LWGEOMs are deep-copied is because the POINTARRAYs within 
LWGEOM *obtained from PostgreSQL* MUST be immutable. Hence if we wish to 
alter a LWGEOM, we *MUST* copy it and return the copy.

And why is this? It's because when PostgreSQL passes us a geometry, we 
are passed a copy of the geometry allocated by PostgreSQL. But the 
LWGEOM deserialization code sets the POINTARRAY pointer directly to the 
doubles array within the PostgreSQL geometry - hence the memory within 
the POINTARRAY *is not ours to free*. This is why there are lots of 
separate lwfree(line->pa)-type calls scattered around liblwgeom to free 
the parts we know can be discarded, but otherwise the memory has to be 
freed by PostgreSQL.

Since I've been spending a lot of time re-working liblwgeom over the 
past few months, I (and I think you also) have separately come to the 
conclusion that having this type of memory model is not good. The 
principle of least surprise dictates that lwfree()-ing a geometry should 
free all of it, and not assume any behaviour on the part of the 
environment using the geometry.

Part of the testing I was doing over Christmas involved experimenting 
with memcpy() to see what the impact would be of copying the POINTARRAY 
out of the PostgreSQL allocated geometry so that the geometries are 
separate - and I came up with some very surprising results. I know strk 
was keen to optimise the performance of the LWGEOMs, but from my results 
I think there has been a case of premature optimisation here.

The attached file testmem.c is used to compare the performance of LWGEOM 
  construction on an array of 80,000 2D points. The first test is 
designed to compare the difference between scanning through the point 
array using the existing getPoint2d_p() function (unaligned memcpy 
access) and scanning through an aligned array of doubles:

Testing unaligned point access...
x: -2.6378e+08
y: -3.66648e+08
x: 2.13081e+09
y: 8.59704e+08
x: 1.01699e+09
y: -1.04434e+09
x: 4.88672e+08
y: 6.35536e+08
x: -5.43084e+08
y: -6.452e+08

Execution time: 0.26586 s
(Speed: 300910 points per second)

Testing aligned point access...
x: -2.6378e+08
y: -3.66648e+08
x: 2.13081e+09
y: 8.59704e+08
x: 1.01699e+09
y: -1.04434e+09
x: 4.88672e+08
y: 6.35536e+08
x: -5.43084e+08
y: -6.452e+08

Execution time: 0.0176489 s
(Speed: 4.53285e+06 points per second)

Wow. This goes back to your original idea with respect to the speed of 
aligned/versus unaligned access and we can see that the aligned version 
blows away the unaligned version in terms of access speed. So then the 
question to ask is that if we were to memcpy() the unaligned point array 
into an aligned double array when constructing the LWGEOM, would this 
still be faster than access the unaligned array? And the answer is a 
resounding yes:

Testing non-memcpy lwline constructor with point iteration...

Execution time: 1.01137 s
(Speed: 79100.2 points per second)

Testing memcpy lwline constructor with point iteration...

Execution time: 0.368717 s
(Speed: 216969 points per second)

This test shows the time taken to memcpy() the POINTARRAY and also 
iterate through all of the points within it. The results clearly show 
that if we visit every point in the geometry (which we have to do if we 
call serialize to send the LWGEOM back to PostgreSQL anyway), then even 
with the initial memcpy() from unaligned to aligned memory, the aligned 
version is still nearly 3 times faster than the unaligned version! :O

Now there is a slight degenerate case here: what if we simply want to 
access a single point within the geometry? This is demonstrated by this 
case here:

Testing non-memcpy lwline constructor with single point access (middle 
point)...

Execution time: 0.0055759 s
(Speed: 1.43475e+07 points per second)

Testing memcpy lwline constructor with single point access (middle point)...

Execution time: 29.0237 s
(Speed: 2756.37 points per second)

Ouch. So if we don't visit all points within the memcpy() point array 
then the overhead of the memcpy() becomes quite substantial. This then 
led me to think about LWGEOM_INSPECTED which is supposed to be for 
high-speed access - perhaps we can make use of this? Unfortunately this 
makes use of the serialized form which is only something that would be 
useful to PostGIS and not other users of liblwgeom. But it still makes 
sense to offer a non-memcpy() alternative read-only LWGEOM derivative 
for these cases.

So in summary, based upon this work I would suggest the following 
recommendations:

- Alter the deserialize routines to memcpy() the unaligned pointarray 
into aligned liblwgeom allocated memory

- Swap liblwgeom code over access the arrays directly instead of using 
getPoint2d_p()

- Alter the collection manipulation routines so that they no-longer deep 
copy LWGEOMs

- Alter the lwfree_* functions so that they free the pointarray copy

Once liblwgeom manages its own memory in this way are then very close to 
getting rid of the bad hack that is lwgeom_init_allocators() and 
lwgeom_install_default_allocators().

Then just to complete the icing on the cake:

- Remove the LWGEOM_INSPECTED routines (I think given the non-alignment 
of these they will also prove to be slower in real life)

- Create a new LWGEOM_INLINE read-only type which works in a similar 
manner to existing LWGEOM without memcpy(). We can then use this for 
pulling out single unaligned points out of large arrays if required.

I realise that this is quite a long email, but I think that the attached 
test show there is a strong case for changing the way in which liblwgeom 
which will not only speed up performance for routines which process 
geometries, but will also untangle the liblwgeom memory-management from 
PostgreSQL (which as Paul notes will make it much easier to detect 
memory leaks) :)

ATB,

Mark.

-- 
Mark Cave-Ayland
Sirius Corporation - The Open Source Experts
http://www.siriusit.co.uk
T: +44 870 608 0063
-------------- next part --------------
A non-text attachment was scrubbed...
Name: testmem.c
Type: text/x-csrc
Size: 3962 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20090107/395343a7/attachment.c>