Announcing jhc 0.7.4! There have been a few major changes, the main one being that there is now support for a garbage collector. This drastically increases the number of programs which are feasable to compile with jhc. http://repetae.net/computer/jhc/ Any testing people can do with -fjgc would be greatly appreciated! My gameplan is to fix any issues that come up with the new gc and release a 0.7.5 that will have the GC enabled by default. This will probably be the first version of jhc I can recommend to non-developers with a good concience :). Once that is done I can implement a good strategy for library compatibility with other compilers and the standards. As it is, jhc has a mix of haskell 98 and haskell 2010 and the ghc base as its distributed libraries, basically whatever I found I needed in practice I added as I went along. This won't work in the long run. Major changes * a garbage colletor which can be enabled with '-fjgc' is available. after some more testing, I will make it the default in the 0.7.5 release. * A new memory allocator based on Jeff Bonwick's slab memory allocator for kernels. This means that in many cases, memory can be pulled off a slab and immediately used with no initialization, in addition, it allowed a rearrangement of the GC meta-data to optimizally use the cache. * packed representation of algebraic types, 'Maybe Foo' is actually represented in memory as a NULL pointer or just a 'Foo' with no tag bits. Combined with the slab allocator, this can double the number of some common values that can be put in a cache line. * some intense profiling of generated code and modification of the rts and code generator. Signifigant speed-ups in compiled programs are the result. Some other changes since 0.7.3 are * documentation updates, especially when it comes to the runtime. * ghc 6.12 support (it is in fact required now.) * no more monolithic 'Main'. the core pass moved to E.Main and the grin pass moved to Grin.Main. * generated C code is more compact and easier to debug. * more use of bytestring internally, improved performance * JHC_RTS_INCLUDE flag allows including the rts from an external file. useful for debugging/developing the RTS. * explicit register support in grin, for alternate back ends such as a NCG * Removed all compiler magic dealing with Eq,Bounded,Ord, and Bits. instances for these are specified in haskell code even for built in types now. * cleaned out some obsolete flags and options on command line. * updated applicative and support for newest version of 'containers' library. * bug updates * various bug fixes Below is the announcment for 0.7.3 in case you missed it. It's been a long time coming, but jhc-0.7.3 is here. If you have been following the darcs repository, there are not a whole lot of new changes, but there have been substantial fixes since 0.7.2. http://repetae.net/computer/jhc/ One of the most important ones is I have begun the process of standardizing on YAML for all external interfaces that may be useful to automation, this should make interfacing jhc with external tools written in any language much easier, and it will prevent me from spending time trying to invent proprietary formats every time I think of something new to spit out. right now it is used in 3 places: - dumping dependency info with --deps - library dumping with --list-libraries -v - annotating source code, for inputting to documentation generators via --annotate-source The main place it isn't used yet that I desire too is to replace the 'cabal' library description format with a true YAML file. jhc cabal files were never quite compatible with cabal ones anyway and naming them the same thing has been a source of connfusion. some of the other changes have been: features: - a lot more regression tests, many user submitted bugs are now regressions - support for using 'mock' to build rpms - System.Exit, System.Cmd added to base - better compatibility with ghc in some library functions - ui improvements in showing progress and errors - extended --list-libraries info - --deps dependency dumping - more francise compatible thanks to patches from droundy - more instances for bigger tuples added - uses editline if readline not available - select libraries by hash as well as version - add System.IO.Pipe - detect version of gcc needed for cross compiling to windows performance: - storage analysis - a very basic region inference enabled by default - deadcode analysis can see through partial applications now - profiled and sped up some library routines that were producing inellegant core. - figure out when top level grin functions call themselves recursively and turn them into explicit loops. bug fixes: - do expression in infix - fix strict newtype bug - U2U bug fixed - desugaring inside of list comprehensions fix - c generator doesn't mess up on unknown values - the compiler version is stored in the cache files, so multiple versions of jhc don't clobber each others cache entries - Ord instance for lists fixed - recursive type synonyms detected properly - make sure errno.h is included when errno is referenced - don't give a parse error when seeing ghc extensions to INLINE - qualified method names fix -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/
Great work.
* a garbage colletor which can be enabled with '-fjgc' is available. after some more testing, I will make it the default in the 0.7.5 release. * A new memory allocator based on Jeff Bonwick's slab memory allocator for kernels. This means that in many cases, memory can be pulled off a slab and immediately used with no initialization, in addition, it allowed a rearrangement of the GC meta-data to optimizally use the cache.
That sounds like you're essentially using BIBOP (big bag of pages, http://www.memorymanagement.org/glossary/b.html#bibop). Did you compare the overheads with the header-based scheme? Do you still need a tag/header word or do you get the tag by looking up the per page info? Do you use this scheme for all objects or only for small objects? I could imagine a hybrid scheme where where you use bibop for, say, single-constructor objects, although I wonder how you would deal with thunks and their update.
* packed representation of algebraic types, 'Maybe Foo' is actually represented in memory as a NULL pointer or just a 'Foo' with no tag bits. Combined with the slab allocator, this can double the number of some common values that can be put in a cache line.
Interesting. How do you distinguish 'Just e' from 'Just _|_'? Do you need the whole program assumption to disprove that the latter case can happen? / Thomas
On Tue, Jul 27, 2010 at 12:42:27AM +0100, Thomas Schilling wrote:
* a garbage colletor which can be enabled with '-fjgc' is available. after some more testing, I will make it the default in the 0.7.5 release. * A new memory allocator based on Jeff Bonwick's slab memory allocator for kernels. This means that in many cases, memory can be pulled off a slab and immediately used with no initialization, in addition, it allowed a rearrangement of the GC meta-data to optimizally use the cache.
That sounds like you're essentially using BIBOP (big bag of pages, http://www.memorymanagement.org/glossary/b.html#bibop). Did you compare the overheads with the header-based scheme? Do you still need a tag/header word or do you get the tag by looking up the per page info? Do you use this scheme for all objects or only for small objects? I could imagine a hybrid scheme where where you use bibop for, say, single-constructor objects, although I wonder how you would deal with thunks and their update.
Yeah, it is somewhat similar to that, except I don't need to look up in a table what the type is, I just take the address modulo the block size and there is a shared info section at the front of the block. all the GC bookeeping bits are kept here too and can usually fit on a single cache line, that way you can mark a object used without actually having to dereference a pointer to it, allowing the cache line for the object itself to fill hopefully by the time I get around to it on the grey list. objects that contain no pointers are never touched by the GC, an advantage of keeping the bookeeping bits away from the objects. There is no per object overhead/tag word imposed by the storage manager, other than the one or two bits used by the GC. (one bit right now, but I will need to expand it to add some GC features that are missing (destructors, incremential collection)). I currently use this scheme for all objects, however, beyond a certain size I think a header approach might be better, so I will look into that. In particluar, my arrary sizes are limited to what can fit in a block right now when you have the GC on, which is a limitation I need to fix. I did experiment with a header scheme, however, it was never really optimized that well so I don't think I could make performance conclusions from it. I may add a switch to control this though. Honestly, a slab inspired allocator has been my plan since day one of writing jhc, I had a fair amount of experience with them from my previous OS work and felt they would be a good fit for jhcs model.
* packed representation of algebraic types, 'Maybe Foo' is actually represented in memory as a NULL pointer or just a 'Foo' with no tag bits. Combined with the slab allocator, this can double the number of some common values that can be put in a cache line.
Interesting. How do you distinguish 'Just e' from 'Just _|_'? Do you need the whole program assumption to disprove that the latter case can happen?
each word has two tag bits, one says whether the value is in WHNF, the other says whether it should be followed by the GC. So to eval something, I check the tag bit, if it says WHNF I am done, otherwise the object must be one of a thunk or an indirection, if it is a thunk, it has a code pointer as its first entry, otherwise it is a redirection that _must_ be a WHNF pointer. Unlike ghc, there are strong invarients about what sort of objects can appear where, WHNF and non WHNF values actually have different types in Grin and C. For instance, an indirection to an indirection is impossible, as is redirecting a whnf value, this also means a lot of things that are easy for ghc, a collector that moves things around incrementally, implementing concurrent locks by overwriting an evaluation pointer, etc are difficult in jhc. So there are tradeoffs. (a selectable alternate RTS may mitigate this though) Now, the interesting thing is that if the WHNF bit is set, there are no rts or gc imposed restrictions on the word whatsoever, it need not even be a pointer, and often isn't. (unless the gc flag is set, in which case it has to be a heap pointer, but the format of what it is pointing to is completly undefined). For instance, data Foo !Word8 !Word8 will theoretically be packed directly into the word itself as the two most signifigant bytes. For each type I can statically generate an "optimal" layout based on its structure. For instance, maybe benefits from two of these optimizations, first of all, nullary constructors (Nothing) need never appear in the heap, so they are given values that pack directly into a word, this happens for all nullay constructors in general. Then, since there is only one constructor left (Just) we can discard the tag field, because if something of type Maybe, is in WHNF, and is not Nothing then in must be a Just. so the Just is a single heap allocated word (which are packed end to end in a page with no overhead) I am refining the optimization algorithm, on 64 bit machines I have another few bits to play with for instance that I can take advantage of. A particularly nice case is that characters can be fully integreated into the word, so the entire space usage of "Hello" is 10 words as lists benefit from the same packing benefits as Maybe. compare this to 30 or so words used in a traditional "everything is on the heap and tagged" model. The manual has a section describing the RTS, it doesn't describe the GC though, but talks about how I pack things in the pointers. http://repetae.net/computer/jhc/manual.html#the-run-time-system John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/
participants (2)
-
John Meacham -
Thomas Schilling