This release is 90% contributions. Thanks to all who are using YAJL and taking the time to push me patches.

YAJL source is moved to a publically visible repository with full history preserved:
http://code.google.com/p/yajl-c

Changes in 0.4.0

• lth buffer overflow bug in yajl_gen_double s/%lf/%g/ - thanks to Eric Bergstrome
• lth yajl_number callback to allow passthrough of arbitrary precision numbers to client. Thanks to Hatem Nassrat.
• lth yajl_integer now deals in long, instead of long long. This combined with yajl_number improves compiler compatibility while maintaining precision.
• lth better ./configure && make experience (still requires cmake & ruby)
• lth fix handling of special characters hex 0F and 1F in yajl_encode (thanks to Robert Geiger)
• lth allow leading zeros in exponents (thanks to Hatem Nassrat)

enjoy!
--lloyd

w00t. An email from matz, and a little spelunking in the ruby subversion repository shows that there's some tinkering going on in ruby garbage collection land. Here are the interesting change logs:

r15674 | matz | 2008-03-03 01:27:43 -0700 (Mon, 03 Mar 2008) | 5 lines

* gc.c (add_heap): sort heaps array in ascending order to use
  binary search.

* gc.c (is_pointer_to_heap): use binary search to identify object
  in heaps.  works better when number of heap segments grow big.

and...

r16194 | matz | 2008-04-25 03:03:32 -0600 (Fri, 25 Apr 2008) | 7 lines

* gc.c (free_unused_heaps): preserve last used heap segment to
  reduce malloc() call.

* gc.c (HEAP_SIZE): use smaller heap segment (2K) for more chance
  to be freed.  based on patch from authorNari .

* gc.c (rb_newobj_from_heap): eventually allocate heap segments.

So now in ruby 1.9 trunk we're keeping heaps in sorted order by memory address, and using binary search to answer the is_pointer_to_heap() question quickly. This optimizes things to the point where we can really crank down heap size. Smaller heaps means more OS reclaimation, means reduced resource usage, and should even mean a ruby with reduced COW badness. All this at a minimal performance impact for normal execution (maybe none, matz knows).

So applause to open source, and matz specifically for sifting through all the ideas/hacks/and patches to realize this thing. It will be interesting to include 1.9 in the performance comparison table to see how things have changed from 1.8.6 to present trunk.

So why do I care so much about a less memory intensive ruby? Well because ruby _really_ shines as an embedded language. In terms of the presence of a robust set of built-ins, and a fairly modest size hit. Also, the C api for embedding is beautiful. It's fun to use in the way that ruby itself is. I'm guessing that the embedding API got so nice because extension authors have been using it and complaining about it for a while. So the part of the api that is common to authoring extentions and embedding an interpreter is great. What sucks is the part that's unique to embedding. It would be great if:

1. I could ruby two ruby interpreter contexts in a single process in different threads (I know this would have some benefits in web server plugins too).
2. if I could have multiple interpreter contexts around at the same time.
3. To be able to cleanly shutdown and restart the interpreter, without massive memory leaks.

So reducing memory usage is a first good step to making ruby the premier language for embedding. Next steps include getting rid of all them statics and breaking and making optional the stuff that is only required by the ruby interpreter itself. Perhaps a bit more ambitious than hackin on the GC...

till the next,
lloyd

Many apologies for my lack of attention to yajl. I've been slowly integrating fixes and change requests from folks, and have moved the source into code.google.com for direct read only svn access.

I've got a couple more reported bugs to work out (mostly around number parsing), and have a contributed C++ wrapper from Neville Franks that I'd like to integrate as an optional additional library.

Truth be told my day job has been consuming all of my time. In coming weeks I expect this to lighten up a tad and to have time to complete what will become yajl 0.4.0.

stay with me,
--lloyd

This is my original writeup on possible improvements to the ruby garbage collector. Latest status is archived in projects/ruby.

overview

Ruby's GC & heap implementation uses a lot of memory. The thing is based around the idea of "heaps". Heaps are chunks of memory where ruby objects are stored. Each heap consists of a number of slots. Slots are between 20 and 40 bytes, depending on sizeof(long). When ruby runs out of heap space, it first does a GC run to try to free something up, and then allocates a new heap. the new heap is 1.8 times larger than the last. Every time a GC run happens, the entire heap is written to turn off mark bits, these are stored in the heap. Then we run through top level objects, and mark them, and all their descendents. Then we throw away anything that's not marked (sweep). Because of the way ruby works, objects may _never_ be moved around in heaps. That means from the time they're allocated to the time they're freed they may not be moved to a new memory address.

So this is a very terse summary, more is available in the ruby hackers guide. But it's enough. There are a couple bad things here.

1. in order for a heap to be reclaimed, _all_ entries on the heap need to be freed. The bigger a heap is, the more likely that it will contain at least one long lived object. The 1.8 growth factor makes it bloody unlikely that you'll ever get to reclaim heap space.
2. A big heap makes GC slower. You have to scan the whole thing
3. (this guy gets the credit on this idea) Because we do scanning copy on write semantics are blown. you do a fork, and as soon as GC runs, your whole heap is resident and private memory.
4. We cannot do compaction at GC time, we must either change the way ruby works in a very fundamental way (bad), or think of a creative lightweight way to just keep the heap compacted.

Plan of attack

1. develop a method of quantifying performance of ruby GC & heap
2. prove some of these ideas can have positive effects in terms of memory usage and performance
3. produce patches for the ruby community and anyone who wants em
4. drink beer

Quantifying

First thing we need is a way to get a look at statistics of the gc stuff. So we hack in a GC.heap_info function that returns

• num_heaps - the number of allocated heaps
• heap_slots_free - the total number of free slots
• heap_memory - the amount of memory allocated to ruby heaps
• heap_slots_allocated - the total number of available slots
• heap_slots_used - the total number of used slots
• num_gc_passes - the number of times GC has been run

Great. Next we need test cases. I start with three:

• grow array build a buncha arrays bigger and bigger
• shrink array start with a big array, build a buncha ones smaller.
• PLIST parsing Parse a huge plist file.

Yeah, they're artificial, but we'll add more cases as we go. At least we have some constant tests to start with.

Proof of concept

hypothesis

By getting rid of the 1.8 growth factor, and making heaps smaller, we can increase the amount of memory that's reclaimed. And make ruby faster, by reducing the amount of scanning unused memory that occurs.

data

Vanilla ruby:

running cases/growarray.rb
 heap before (mem/used slots/% free/heaps/gc passes) 560080/6501/0.767838011570602/2/9
 heap after (mem/used slots/% free/heaps/gc passes) 560080/6367/0.772623384043997/2/11
 time 1.339915
running cases/plist.rb
 heap before (mem/used slots/% free/heaps/gc passes) 15056520/559048/0.257393875553088/7/21
 heap after (mem/used slots/% free/heaps/gc passes) 15056520/109351/0.854744633172117/7/23
 time 3.773354
running cases/shrinkarray.rb
 heap before (mem/used slots/% free/heaps/gc passes) 560080/7537/0.730840654238983/2/9
 heap after (mem/used slots/% free/heaps/gc passes) 560080/6373/0.77240911363474/2/11
 time 1.338151

Killing 1.8 growth factor:

running cases/growarray.rb
 heap before (mem/used slots/% free/heaps/gc passes) 400080/6501/0.674982501749825/2/9
 heap after (mem/used slots/% free/heaps/gc passes) 400080/6367/0.681681831816818/2/11
 time 1.337504
running cases/plist.rb
 heap before (mem/used slots/% free/heaps/gc passes) 9406200/380442/0.191001631002226/47/51
 heap after (mem/used slots/% free/heaps/gc passes) 9406200/109351/0.767468416609429/47/53
 time 4.278476
running cases/shrinkarray.rb
 heap before (mem/used slots/% free/heaps/gc passes) 400080/7525/0.623787621237876/2/9
 heap after (mem/used slots/% free/heaps/gc passes) 400080/6373/0.681381861813819/2/11
 time 1.343519

Killing 1.8 growth factor and reducing heap size to 1/10th

running cases/growarray.rb
 heap before (mem/used slots/% free/heaps/gc passes) 221540/6491/0.413428519790349/11/18
 heap after (mem/used slots/% free/heaps/gc passes) 221540/6368/0.424543647207663/11/20
 time 1.351549
running cases/plist.rb
 heap before (mem/used slots/% free/heaps/gc passes) 7741680/382475/0.0109718192584778/366/365
 heap after (mem/used slots/% free/heaps/gc passes) 3795580/109350/0.423259493670886/179/367
 time 7.971707
running cases/shrinkarray.rb
 heap before (mem/used slots/% free/heaps/gc passes) 221540/7717/0.302638713175493/11/17
 heap after (mem/used slots/% free/heaps/gc passes) 221540/6374/0.424001445870233/11/19
 time 1.343365

analysis

note "heap before" means "heap before final GC run". We fork a process which runs the test case, then we check out the heap using GC.heap_info, then we run a GC pass, then we check it out again.

w00t! we made ruby twice as slow! Well hold on. First inspect the run times of plist.rb (the most realistic test case). Also inspect the number of gc passes. Pretty tight correlation, right? reducing heap size, and removing the 1.8 growth factor both increase the number of gc passes that we make. So we see a significant performance degradation proportional to the number of passes that are run.

Inspect memory usage (still looking at only plist.rb). Vanilla ruby is using 15mb. At the end of everything, and that heap is 85% unused. Kill the 1.8 and we're using 9mb of heap space, 76% unused. Decrease the heap size, and we actually see memory being reclaimed. After the run and final GC we've only got ~4mb in use at 42% free. Immediately after the run we were around 8mb.

parting shot/conclusion

By changing two constants we can make ruby a lot more memory efficient, and at the same time a lot slower. The slow down appears to be largely from increased frequency of GC. Maybe we can look at not running GC _every_ heap allocation, but every N heap allocations... Goal here being to restore ruby to it's original, or better performance characteristics, but reduce the memory usage.

Essence here is that everyone knows you can grow a buffer by a factor and make things faster. But other aspects of ruby make that choice perhaps not optimal here. Stay tuned, we'll dig further.

one more thing, ideas on "automatic heap compaction"

a global freelist? bad. Why not have per-heap freelists. Why not sort the heaps by usage percentage at the end of a sweep? Allocate the heaviest used ones first... There's some complexity here around when GC is run... Cause it's only run when everything is full... But perhaps some room for exploration...

Here's the Problem: http://lists.apple.com/archives/x11-users/2007/Oct/msg00065.html

Here's a proposed "fix": http://aaroniba.net/articles/x11-leopard.html

If they didn't add RPATH support, DTrace, and pretty much avoid judicious changes, I'd be throwing stones. As it stands, this is extremely annoying, but tolerable. Looking forward to the fix...

-lloyd