396007 - Using posix_memalign for GC arenas when mmap is not available

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P2)

Description

[Igor Bukanov]

Bug 392263 uses mmap/VirtualAlloc to implement the allocation of aligned GC arenas using non-executable CPU pages. When the paged allocation is not available or can not be used due to an unsuitable size of the CPU page, the code switches to over sized malloc calls to implement aligned allocation.

It would be nice to use posix_memalign instead when available and avoid malloc overhead.

Comment 1

[Stuart Parmenter]

With jemalloc Windows we support posix_memalign.  Linux has it.  Doesn't seem to be on Mac, but would be nice to use it where possible.

Comment 2

[Igor Bukanov]

Attachment: v1 (something that just compiles)

I will test/document this tomorrow.

Comment 3

[Stuart Parmenter]

fwiw this patch seems to work OK on Windows with jemalloc (with some forced #ifdefs)

Comment 4

[Igor Bukanov]

(In reply to comment #3)
> fwiw this patch seems to work OK on Windows with jemalloc (with some forced
> #ifdefs)
> 

what is the overhead of memalign in jemalloc? In particular, does it need any headers/trailers? if so, calling the function several times like in

    memalign(&p, 2^n, 2^n);

would not be able to allocate the blocks in a sequence but would make inssted a holes of size 2^n at least between blocks. A proper way to use the function would be to decrease the allocation size:

     memalign(&p, 2^n, 2^n - implementation_overhead);

Comment 5

[Jason Evans]

jemalloc does not use object headers, so the objects would all be adjacent, assuming no pre-existing memory fragmentation.

Comment 6

[Stuart Parmenter]

I think we're going to want to do larger allocations than 1k for these.  With your patch I see 328200 NewGCChunk()s vs 1500 with the defaults on Windows

Comment 7

[Igor Bukanov]

(In reply to comment #6)
> I think we're going to want to do larger allocations than 1k for these.  With
> your patch I see 328200 NewGCChunk()s vs 1500 with the defaults on Windows
> 

why is it necessary bad? The amount of allocated memory for GC heap is the same in both cases. But in the memalign case the system can use for its purposes the space that is otherwise wasted due to internal fragmentation.

Comment 8

[Igor Bukanov]

(In reply to comment #5)
> jemalloc does not use object headers, so the objects would all be adjacent,
> assuming no pre-existing memory fragmentation.

This is nice. Still, since posix_memalign from GLIBC does use the header for posix_memalign, I would like to support that in the patch automatically detecting header's size during compilations.  

Does a build where posix_memalign comes from jemalloc defines any special preprocessor macros?

Comment 9

[Igor Bukanov]

(In reply to comment #3)
> fwiw this patch seems to work OK on Windows with jemalloc (with some forced
> #ifdefs)

But how MSVC can find a definition of posix_memalign??? The patch does not try to include any extra headers assuming that posix_memalign comes from stdlib.c. Or does MSVC comes with posix_memalign defined in that header?

Comment 10

[Igor Bukanov]

Attachment: v2

The new version passes the tests when compiled with -DJS_GC_USE_MMAP=0 on Linux. To enable posix_memalign on a Windows build with jemalloc, make sure that the following defines are passed to the compiler when it compiles jsgc.c:

 -DJS_GC_USE_MMAP=0 -DJS_HAS_POSIX_MEMALIGN=1 -DJS_GC_AREANA_PAD=0

To finish the patch I need to set JS_HAS_POSIX_MEMALIGN and JS_GC_AREANA_PAD automatically on Windows when jemalloc and its posix_memalign is available. Does jsemalloc provides any preprocessor macros for that?

Comment 11

[Igor Bukanov]

Attachment: v3

The new patch detects jemalloc build via checking MOZ_MEMORY and enables posix_memalign support if so. Since a default posix_memalign from GLIBC suffers from the problem in comment 4, the patch introduces JS_GC_ARENA_PAD to ask for less memory than the alignment requirements. With jemalloc it is set to 0, otherwise JS_GC_ARENA_PAD it is 2 words, the size that GLIBC needs.

The patch also uses 4K arenas with all the allocation modes. Small arenas apparently hurt the performance with posix_memalign from jemalloc.

To enable posix_memalign allocations with the patch, make sure that JS_GC_USE_MMAP is set to 0 when compiling SpiderMonkey. I.e. like passing -DJS_GC_USE_MMAP=0 to the compiler.

Comment 12

[Igor Bukanov]

If testing shows that jemalloc is better for the browser, then code can be changed to favor posix_memalign over mmap when MOZ_MEMORY is defined.

Comment 13

[Igor Bukanov]

Attachment: v4

The new version optimizes more for the case when GC arena == GC chunk and excludes unnecessary code in this case.

Comment 14

[Igor Bukanov]

Attachment: sunspider using psix_memalign

With a default allocator from GLIBC enabling posix_memalign on Linux leads to 2.5% improvement in SunSpider benchmark with optimized thread-safe build of js shell. This is for Fedora-9 alpha on Pentium-M 1.1GHz laptop.

Comment 15

[Igor Bukanov]

Attachment: v5

The new version prioritize posix_memalign over mmap when both are available. This is based on the benchmark results from Linux. It would be interesting to know  what happens on Windows.

Comment 16

[Igor Bukanov]

Attachment: v6

The previous version was over-engineered. The new version always uses posix_memalign when it is available and the user does not insist on mmap with explicit JS_GC_USE_MMAP set to 1.

Comment 17

[Brendan Eich [:brendan]]

What is the win (SunSpider or any other test we use) on Windows with jemalloc and this patch?

/be

Comment 18

[Brendan Eich [:brendan]]

Comment on attachment 304758 [details] [diff] [review]
v6

>+ * When it is is true, a platform-dependant function like mmap is used to get
>+ * memory aligned on CPU page boundary. If the macro is false or not defined,
>+ * posix_memalign is used when available. Otherwise the code uses over-
>+ * sized malloc to allocate a chunk with js_gcArenasPerChunk aligned arenas.
>+ * The approximate space overhead of this is 1/js_gcArenasPerChunk. For
>+ * details, see NewGCChunk/DestroyGCChunk below.

Please rewrap to avoid ragged right, oversized (one word) fits on one line.

>+     * Implement the chunk allocation using over sized malloc if mmap or

s/over sized/oversized/ and any others like these.

r/a=me, looks good -- anticipate Windows win too (may have heard about it, didn't see it reported here).

/be

Comment 19

[Igor Bukanov]

(In reply to comment #17)
> What is the win (SunSpider or any other test we use) on Windows with jemalloc
> and this patch?

Robert has mentioned on IRC that with the initial version of the patch that has used 1 K GC arenas things were slower by couple percent, with bigger arenas the speedup was 2%. According to this the last version of the patch uses 4K arenas in all arena allocation modes.

   

Comment 20

[Igor Bukanov]

Attachment: v6b

The new version addresses the nits from comment 18.

Comment 21

[Igor Bukanov]

Attachment: v7

The landed patch from bug 400902 added expected heavy conflicts with this patch. While resolving them I took opportunity to improve the patch when it is known at the compile time that GC arena == chunk.  Now the code uses bitfields in JSGCArenaInfo only if a chunked allocation is necessary.

Comment 22

[Igor Bukanov]

Comment on attachment 305852 [details] [diff] [review]
v7

The last version has passed both the test suite and mochi tests.

Comment 23

[Igor Bukanov]

The last patch compiles on Mac and probably on Windows - the try server http://tinderbox.mozilla.org/showbuilds.cgi?tree=MozillaTry would have already stopped in the case of compilation problems on Windows as SpiderMonkey compiles early during the compilation stage.

Comment 24

[Brendan Eich [:brendan]]

Comment on attachment 305852 [details] [diff] [review]
v7

>+int
>+posix_memalign(void **memptr, size_t alignment, size_t size);

Minimal declaration to get Windows happy, but house style favors extern.

>+ * Declare the headers for mmap unless we have posix_memalign and do not insist

s/Declare/Include/

>+ * memory aligned on CPU page boundary. If the macro is false or not defined,

s/boundary/boundaries/
s/not defined/undefined/

This should still fit in the given tw=78.

>+ * posix_memalign is used when available. Otherwise the code uses oversized
>+ * malloc to allocate a chunk with js_gcArenasPerChunk aligned arenas.

Suggest "... uses malloc to over-allocate a chunk ...".

>+ * The code also allocates arenas in chunks when JS_GC_USE_MMAP is true to

s/true/1/

>+ * the runtime.

Strike "the".

>+ * JS_GC_ARENA_PAD defines the number of bytes to pad JSGCArenaInfo structure.
>+ * It is used to improve allocation efficiency when using posix_memalign. If
>+ * its implementation uses internal headers, then calling

s/its/malloc's/

>+ * due to the need to fit headers. JS_GC_ARENA_PAD allows to mitigate that

s/allows to mitigate/allows us to mitigate/

or (better) just s/allows to mitigate/mitigates/

>+ * The structure is stored in one of chunk's free arenas. GET_CHUNK_INFO_INDEX

"Structure stored in one of a chunk's free arenas."

>+ * macro gives the index of this arena. When all arenas in the chunk are used,

strike "macro" as the lack of definite article "The" before "GET_CHUNK_INFO_INDEX" makes it awkward, and it's arguably deadwood in any case -- the rest of the para should rewrap well.

>+     * Implement the chunk allocation using oversized malloc if mmap or
>+     * posix_memalign are not available.

s/the chunk/chunk/
s/or/and/

>      *
>      * Since malloc allocates pointers aligned on the word boundary, to get
>      * js_gcArenasPerChunk aligned arenas, we need to malloc only
>      *   ((js_gcArenasPerChunk + 1) << GC_ARENA_SHIFT) - sizeof(size_t)
>      * bytes. But since we stores the gap between the malloced pointer and the
>      * first arena in the chunk after the chunk, we need to ask for
>      *   ((js_gcArenasPerChunk + 1) << GC_ARENA_SHIFT)
>      * bytes to ensure that we always have room to store the gap.
>      */

Again blank comment lines on either side of excerpted code, relations, and formulae would be nice.

>     p = malloc((js_gcArenasPerChunk + 1) << GC_ARENA_SHIFT);
>-    if (!p)
>-        return 0;
>-    chunk = ((jsuword) p + GC_ARENA_MASK) & ~GC_ARENA_MASK;
>-    *GetMallocedChunkGapPtr(chunk) = (uint32) (chunk - (jsuword) p);
>-    return chunk;
>+    if (p) {
>+        jsuword chunk;
>+
>+        chunk = ((jsuword) p + GC_ARENA_MASK) & ~GC_ARENA_MASK;
>+        *GetMallocedChunkGapPtr(chunk) = (uint32) (chunk - (jsuword) p);
>+        return chunk;
>+    }

Previous code followed prevailing style by casting out (unlikely) error with early return and well-predicted (IIRC) branch around then clause. Just wondering why this change. Is it better for prefetching?

Looks good, r/a+ with nits picked as appropriate.

/be

Comment 25

[Stuart Parmenter]

Latest patch looks good on Windows.  I tested it and don't see any real perf change on Windows but should be a little better long term.

Comment 26

[Igor Bukanov]

Attachment: v8

The new version of the patch addresses the nits from the comment 24.

> Previous code followed prevailing style by casting out (unlikely) error with
early return and well-predicted (IIRC) branch around then clause.

I wanted to avoid declaring "chunk" at the top of the function as it would require an ifdef around it as only oversized malloc needs it. In the new version I have changed the code to follow the early-return-on-error pattern and used an explicit block to declare "chunk":

     p = malloc((js_gcArenasPerChunk + 1) << GC_ARENA_SHIFT);
-    if (p) {
+    if (!p)
+        return 0;
+
+    {
         jsuword chunk;
 
         chunk = ((jsuword) p + GC_ARENA_MASK) & ~GC_ARENA_MASK;
         *GetMallocedChunkGapPtr(chunk) = (uint32) (chunk - (jsuword) p);
         return chunk;
     }
 #endif
-    return 0;

Comment 27

[Mike Beltzner [:beltzner, not reading bugmail]]

Moving bugs that aren't beta 4 blockers to target final release.

Comment 28

[Damon Sicore (:damons)]

Please land this and close it.  Requesting approval for b4.

Comment 29

[Igor Bukanov]

I checked in the patch from comment 26 to the trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%2Fcvsroot&date=explicit&mindate=1204474380&maxdate=1204474414&who=igor%25mir2.org

Comment 30

[timeless]

(In reply to comment #18)
> (From update of attachment 304758 [details] [diff] [review])
> >+ * When it is is true, a platform-dependant function like mmap is used to get

"it is true", "dependent". I'm shocked that brendan didn't complain.

Comment 31

[Igor Bukanov]

(In reply to comment #30)
> (In reply to comment #18)
> > (From update of attachment 304758 [details] [diff] [review] [details])
> > >+ * When it is is true, a platform-dependant function like mmap is used to get
> 
> "it is true", "dependent". I'm shocked that brendan didn't complain.

Thanks for spotting this, I will file a "regression" bug about this".