Re: [Gc] Article about memory fragmentation

--===============8679950845263539592==
Content-Type: multipart/alternative; boundary=001a1130d05aec9cb2053e7447fe

--001a1130d05aec9cb2053e7447fe
Content-Type: text/plain; charset=UTF-8

On Sun, Oct 9, 2016 at 4:40 PM, Paul Bone <[email protected]> wrote:

> I'd like to check that I understand.  By pre-allocating long lived items,
> but not short lived items, we're more likely to guarantees that those
> objects
> are allocated on the same blocks, and not interspersed on other blocks
> preventing those blocks from being freed when the short-lived objects are
> collected?


Right.

In fact there is an existing API which would be useful for this:

void* GC_malloc_many(size_t objSz)

... which is implemented by ...

void GC_generic_malloc_many(size_t objSz, int objKind, void **result)

It might make sense to have GC_malloc_many_atomic() or the uncollectable
variants, but they din't exist at the moment and you can get the effect now
by a direct call to GC_generic_malloc_many.

This call returns some number of objects of the same size (rounded up
minimally -- just to the next multiple of 16 bytes), all of which are
located in the same gc/VM page. The first bytes of each object point to the
next object, and the return value is a pointer to the first object.

The function tries to find an existing block of objects of that size,
allocating an entire new block only if one can't be found. It might make
sense to add a parameter (or another function) to force always using an
entire (new or reclaimed) VM page for the returned list.


 Can you or someone else on the BDWGC tell me in what order blocks are put
> on

the free lists.  Do the free spots in mostly-full blocks appear earlier on
> the free lists?  If things are placed on the free list in the order they
> are
> swept which blocks are swept sooner?
>

First, the free list for objects of a particular size (and kind) always[1]
contain only objects from a single gc/VM page. The objects are ordered by
memory address within the gc page.

When the free list for objects of a particular size is empty, a single page
of objects of the same size is swept and any objects that were not marked
(reachable) at the previous GC are added to the free list. Some objects in
the page may have since become unreachable and this is not detected, but
it's impossible for a previously unreachable object to become referenced --
since it was unreachable by the app :-)

If a page is "nearly full" then it is skipped, on the assumption that it
takes a lot of time for little benefit (speed/space tradeoff).

The order in which pages are swept is determined by the ok_reclaim_list for
blocks with that size of object, linked together by the hb_next field. This
is set up by GC_apply_to_all_blocks() after each GC, which processes pages
in order of memory address.

[1] unless you use GC_free(), in which case anything freed by GC_free() is
at the start of the free list and will be the first object(s) of that
size(&kind) to be returned from GC_malloc().

--001a1130d05aec9cb2053e7447fe
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On S=
un, Oct 9, 2016 at 4:40 PM, Paul Bone <span dir=3D"ltr">&lt;<a href=3D"mail=
to:[email protected]" target=3D"_blank">[email protected]</a>&gt;</span> wrote:=
<br><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bor=
der-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:sol=
id;padding-left:1ex">I&#39;d like to check that I understand.=C2=A0 By pre-=
allocating long lived items,<br>
but not short lived items, we&#39;re more likely to guarantees that those o=
bjects<br>
are allocated on the same blocks, and not interspersed on other blocks<br>
preventing those blocks from being freed when the short-lived objects are<b=
r>
collected?</blockquote><div><br></div><div>Right.</div><div><br></div><div>=
In fact there is an existing API which would be useful for this:</div><div>=
<br></div><div>void* GC_malloc_many(size_t objSz)</div><div><br></div><div>=
... which is implemented by ...</div><div><br></div><div>void GC_generic_ma=
lloc_many(size_t objSz, int objKind, void **result)<br></div><div><br></div=
><div>It might make sense to have GC_malloc_many_atomic() or the uncollecta=
ble variants, but they din&#39;t exist at the moment and you can get the ef=
fect now by a direct call to=C2=A0GC_generic_malloc_many.</div><div><br></d=
iv><div>This call returns some number of objects of the same size (rounded =
up minimally -- just to the next multiple of 16 bytes), all of which are lo=
cated in the same gc/VM page. The first bytes of each object point to the n=
ext object, and the return value is a pointer to the first object.</div><di=
v><br></div><div>The function tries to find an existing block of objects of=
 that size, allocating an entire new block only if one can&#39;t be found. =
It might make sense to add a parameter (or another function) to force alway=
s using an entire (new or reclaimed) VM page for the returned list.</div><d=
iv><br></div><div><br></div><blockquote class=3D"gmail_quote" style=3D"marg=
in:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,20=
4);border-left-style:solid;padding-left:1ex">=C2=A0Can you or someone else =
on the BDWGC tell me in what order blocks are put on</blockquote><blockquot=
e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width=
:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-lef=
t:1ex">
the free lists.=C2=A0 Do the free spots in mostly-full blocks appear earlie=
r on<br>
the free lists?=C2=A0 If things are placed on the free list in the order th=
ey are<br>
swept which blocks are swept sooner?<br></blockquote><div><br></div><div>Fi=
rst, the free list for objects of a particular size (and kind) always[1] co=
ntain only objects from a single gc/VM page. The objects are ordered by mem=
ory address within the gc page.</div><div><br></div><div>When the free list=
 for objects of a particular size is empty, a single page of objects of the=
 same size is swept and any objects that were not marked (reachable) at the=
 previous GC are added to the free list. Some objects in the page may have =
since become unreachable and this is not detected, but it&#39;s impossible =
for a previously unreachable object to become referenced -- since it was un=
reachable by the app :-)=C2=A0</div><div><br></div><div>If a page is &quot;=
nearly full&quot; then it is skipped, on the assumption that it takes a lot=
 of time for little benefit (speed/space tradeoff).</div><div><br></div><di=
v>The order in which pages are swept is determined by the=C2=A0ok_reclaim_l=
ist for blocks with that size of object, linked together by the hb_next fie=
ld. This is set up by=C2=A0GC_apply_to_all_blocks() after each GC, which pr=
ocesses pages in order of memory address.</div><div><br></div><div>[1] unle=
ss you use GC_free(), in which case anything freed by GC_free() is at the s=
tart of the free list and will be the first object(s) of that size(&amp;kin=
d) to be returned from GC_malloc().</div><div><br></div></div></div></div>

--001a1130d05aec9cb2053e7447fe--

--===============8679950845263539592==
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: base64
Content-Disposition: inline

X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KZGV2ZWxvcGVy
cyBtYWlsaW5nIGxpc3QKZGV2ZWxvcGVyc0BsaXN0cy5tZXJjdXJ5bGFuZy5vcmcKaHR0cHM6Ly9s
aXN0cy5tZXJjdXJ5bGFuZy5vcmcvbGlzdGluZm8vZGV2ZWxvcGVycwo=

--===============8679950845263539592==--