Action-less GC for faster memory allocation

[gmhwxi]

When compiling an ATS program, you can use

-DATS_MEMALLOC_LIBC // using libc malloc/free
-DATS_MEMALLOC_GCBDW // using malloc/free provided by Bohem-GC

There is a point that some people may not be aware of.

I often use -DATS_MEMALLOC_GCBDW even if my code does not require
runtime garbage collection. For instance,  my code uses linear types to take
care of memory issues. This makes sense because an action-less Bohem-GC
may actually provide faster allocation/deallocation for small memory blocks
(say, few than 128 bytes).

[Raoul Duke]

Does it / could it not also provide a secondary check on leaks?
http://hboehm.info/gc/leak.html

> --
> You received this message because you are subscribed to the Google Groups
> "ats-lang-users" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to ats-lang-user...@googlegroups.com.
> To post to this group, send email to ats-lan...@googlegroups.com.
> Visit this group at http://groups.google.com/group/ats-lang-users.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/ats-lang-users/07cd9a7a-c4b6-46d9-a886-29f89b03e056%40googlegroups.com.

[gmhwxi]

True. I would use Valgrind for leak detection.

[Barry Schwartz]

gmhwxi <gmh...@gmail.com> skribis:

tcmalloc claims to have advantages for small allocations. But I guess
the point is that on most of our systems we can just use Boehm GC like
regular malloc, perhaps with benefit (though on some systems it is
supposed to need special initialization).

Related: Is there a way to get the ATS compiler to straightforwardly
inform you whether the program is likely to have memory leaks and so
benefit from garbage collection? Or really mainly so one can avoid
accidentally leaking memory when trying to avoid GC.

[Hongwei Xi]

>>tcmalloc claims to have advantages for small allocations.

I did try tcmalloc. And also jemalloc. I got worse results than using libc-malloc on several

benchmarks I used. I did not continue further.

I definitely encourage people to investigate this issue further.

--
You received this message because you are subscribed to the Google Groups "ats-lang-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ats-lang-user...@googlegroups.com.
To post to this group, send email to ats-lan...@googlegroups.com.
Visit this group at http://groups.google.com/group/ats-lang-users.

To view this discussion on the web visit https://groups.google.com/d/msgid/ats-lang-users/20141113235330.GA11283%40crud.

[gmhwxi]

>>But I guess
the point is that on most of our systems we can just use Boehm GC like
regular malloc, perhaps with benefit (though on some systems it is
supposed to need special initialization).

One time I had to use libc-malloc instead of the one from Boehm-GC. I
was mixing ATS code with some Java code. Apparently, Java-GC and
Boehm-GC do not like the presence of each other :(

Does anyone know a simple conservative GC that can run along the side of
Java-GC?

[Raoul Duke]

> Does anyone know a simple conservative GC that can run along the side of
> Java-GC?

tinygc mayhaps http://tinygc.sourceforge.net/?

[Barry Schwartz]

Hongwei Xi <gmh...@gmail.com> skribis:

> I did try tcmalloc. And also jemalloc. I got worse results than using
> libc-malloc on several
> benchmarks I used. I did not continue further.

This is with GNU libc?

Here is an overview for a start on investigations:
http://en.wikipedia.org/wiki/C_dynamic_memory_allocation

The only use I have made of jemalloc personally is I have stolen its
generic-C-macros implementation of red-black trees.

[Raoul Duke]

> generic-C-macros implementation of red-black trees.

reminds me of one of my favourite debates:
http://www.read.seas.harvard.edu/~kohler/notes/llrb.html

[Barry Schwartz]

Raoul Duke <rao...@gmail.com> skribis:

> > generic-C-macros implementation of red-black trees.
>
>
> reminds me of one of my favourite debates:
> http://www.read.seas.harvard.edu/~kohler/notes/llrb.html

Evans wrote it already, so I use it. If I had had to write my own, I’d
likely have done AVL trees. :)

I would think Sedgwick is not the best source of a useful opinion on
the difficulty of coding of RB tree variants, due to his closeness to
the subject. One of the lessons from my signal processing education,
for instance, is you need to bring in outsiders and do blind studies
to judge the real-life quality of a telephonic system. :)

[gmhwxi]

Yes, glibc-malloc.

[gmhwxi]

I prefer AVL as well :)

For a red-black tree implementation, you could store the red/black
bit in the pointer pointing to the tree. So you could save a bit (pun).

[Barry Schwartz]

gmhwxi <gmh...@gmail.com> skribis:

> >>But I guess
> the point is that on most of our systems we can just use Boehm GC like
> regular malloc, perhaps with benefit (though on some systems it is
> supposed to need special initialization).
>
> One time I had to use libc-malloc instead of the one from Boehm-GC. I
> was mixing ATS code with some Java code. Apparently, Java-GC and
> Boehm-GC do not like the presence of each other :(

Might I ask what happens?

I have mixed Boehm GC (via Guile) with C-Python’s reference counting
and garbage collector. I’d thought merely using finalizers for Python
objects would do the job, but it turned out I had to use weak
references, make sure the Python GC ran before the Boehm GC was shut
down, etc., etc.

[Barry Schwartz]

gmhwxi <gmh...@gmail.com> skribis:

> I prefer AVL as well :)
>
> For a red-black tree implementation, you could store the red/black
> bit in the pointer pointing to the tree. So you could save a bit (pun).

The jemalloc implementation has an RB_COMPACT option for such a bit of
scrimping. Grab rb.h from a copy of jemalloc (BSD-licensed stuff) if
interested. Probably could be translated fairly directly into ATS
template functions. :)

[gmhwxi]

Sorry, I did not try to debug.

My problem just crashed.

I google-searched around. It seemed that some person reported
a similar issue long time ago and Bohem responded but did not
address it.

My code is here:

https://github.com/githwxi/ATS-Postiats-contrib/blob/master/projects/SMALL/GameOf24/Java/Makefile

You still produce the crash by reading the Makefile first.

[gmhwxi]

problem -> program :)

[Barry Schwartz]

I think gcj uses Boehm GC, if one simply wants to mix Java _source_
code with ATS using Boehm GC. (Though sometimes implementations set
funny options in the GC, which might be a problem.)

[gmhwxi]

I just made my example to work with gcj. But I don't think this
is really that meaningful. I am more inclined to go the atscc2java
route in the future...

[gmhwxi]

>>Related: Is there a way to get the ATS compiler to straightforwardly
inform you whether the program is likely to have memory leaks and so
benefit from garbage collection? Or really mainly so one can avoid
accidentally leaking memory when trying to avoid GC.

I forgot about this question until now.

No. I am not aware of a general way to do this. If there is a strong need
to ensure no leaks, I often do it by hand. That is, I replace datatypes with
linear datatypes while relying on the typechecker to guide me through this
process.

[Barry Schwartz]

I asked:

> >>Related: Is there a way to get the ATS compiler to straightforwardly
> inform you whether the program is likely to have memory leaks and so
> benefit from garbage collection? Or really mainly so one can avoid
> accidentally leaking memory when trying to avoid GC.

gmhwxi <gmh...@gmail.com> replied:

> I forgot about this question until now.
>
> No. I am not aware of a general way to do this. If there is a strong need
> to ensure no leaks, I often do it by hand. That is, I replace datatypes with
> linear datatypes while relying on the typechecker to guide me through this
> process.

The question arose because my first use of a datatype for
pattern-matching, then seeing that ATS asked for a malloc but not for
a free. So I realized I wanted a datavtype. But if I had been
supplying a malloc and free already I might not have noticed.

[gmhwxi]

I see what you meant.

I could have done something really cheap: using ATS_MALLOC_linear for
allocatiing linear constructors and ATS_MALLOC_nonlinear for non-linear ones.
In this way, if one searches for ATS_MALLOC_linear, then it is a sure sign of
leak if no GC is involved.

I feel that this kind of "solution" is too ad hoc. There is a trove of information
generated during compilation that can be useful to the programmer. I plan to find
a way to export such information in, say, JSON format so that people can write
external tools to analyze it.

[Marko Schütz-Schmuck]

Can one express in ATS the requirement that a pointer is appropriately aligned and then have that checked statically?

[gmhwxi]

This issue was discussed here a while ago:

http://sourceforge.net/p/ats-lang/mailman/message/28106374/

memalign.sats is not made into ATS2 as it is too unwieldy to use in practice.

[Marko Schütz-Schmuck]

 I have read source code for AVL trees that assumes aligned pointers and uses an assert for the check for every node created. This is used in ZFS and thus in the kernel of several OSs.

Just how unwieldy in practice in memalign.sats?

[Hongwei Xi]

>>Just how unwieldy in practice in memalign.sats?

I have never really used it.

If I need to do it, I may try something as follows:

Say, ptr_get reads a value of type T from a given pointer:

extern

fun ptr_get{l:addr} (pf: !T @ l | p: ptr(l)): T

If I need to make sure that the given pointer is well-aligned, I can use the following
interface for ptr_get:

extern

fun ptr_get{l:addr} (pf: !T @ l, pf2: is_aligned(l)  | p: ptr(l)): T

where is_aligned is an abstract prop:

absprop is_aligned (l:addr).

Run-time checks can be added to get a proof for the 'is_aligned' predicate.

--
You received this message because you are subscribed to the Google Groups "ats-lang-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ats-lang-user...@googlegroups.com.
To post to this group, send email to ats-lan...@googlegroups.com.
Visit this group at http://groups.google.com/group/ats-lang-users.

To view this discussion on the web visit https://groups.google.com/d/msgid/ats-lang-users/cbd9ce38-509f-49f0-820d-bf5e34901311%40googlegroups.com.