According to Anton Ertl <anton@[EMAIL PROTECTED]
>:
> What file system are you thinking of?
I _think_ some versions of Reiserfs are very fined-grained and thus may
have a lot of space overhead (relatively to the actually stored data).
But this is actually more an issue for a file written out with
lseek()/write() by small chunks. If the file is written through a mmap()
and randomly dirtied pages, then file allocation will occur on a page
basis, which should mitigate the effect.
> So when you say "copying GC", you don't mean what others (e.g., the
> Wikipedia authors) mean by "copying GC"; instead, you mean "moving
> GC". Do you pay the words extra for this?
Well, if you read back the few previous messages, you will notice that
_I_ was talking about "a GC which moves objects" to which _you_ replied
by talking of "the overhead of a copying GC". At that point, I assumed
that you were simply using the term "copying" to mean what I named
"moving", and I adapted my text to your apparent terminology because
that's what courteous people do when they want to ease communication.
> Anyway, back to your example. I can believe that in your 90% full
> situation a compacting memory manager can succeed where a
> non-compacting one fails. But I don't think that GC is more efficient
> than explicit deallocation in this setup.
A compacting memory manager somewhat needs to scan all memory (or keep
track of modifications), at which point transforming the memory manager
into a GC is cheap: most of the hard bits are done -- namely identifying
which data cells are pointers -- and there is a technique called
"pointer reversal" which is quite handy for performing the "mark" phase
without space overhead; my experiment showed that, at least in my
situation, the "compact" phase dominated the cost of the GC.
On the other hand, having a GC means that the main application code did
not need bother with deallocation, which helped in reducing the code
size. The main reason that I had a single megabyte of RAM was that most
of the machine RAM was used by the compiled code; with explicit
deallocation, it is plausible that the megabyte of free RAM would have
become half a megabyte, possibly less.
> Concerning the issue of cache behaviour, one could compare a GC that
> is supposed to have the cache benefit (any copying GC? Or only some
> specially designed one), and compare it with other GCs. Is the
> overall cache behaviour really better with the copying GC across a
> large set of programs? And how about the overall cost?
If you mean that assessing the benefits and costs asssociated with
a specific memory management techniques is a hard problem then I
fully support you. Microbenchmarks cannot really help you there.
As for the cache benefit, it is documented by Jones and Lins to require
a specifically designed GC. Actually, the most simple copying GC
(scavengers with breadth-first traversal) tend to do the "wrong" thing
and to suffer from bad behaviour with regards to the cache. Jones and
Lins cite articles from Zorn, who claims that on "typical" programs,
creation order is a good approximation of usage order. My mark-compact
GC preserved creation order and thus _should_ be good with regards to
cache behaviour.
> The 10% overhead of array bounds checking is for the case where array
> bounds checking is not optimized at all. It should get smaller if Sun
> applied any bounds checking optimization.
It probably depends on what type of code they take for the estimate. One
of my main examples is the RC4 cipher. It is very simple and centered
around an array of 256 bytes, which is heavily accessed. When I
translate the Java version to C code, and then compile it with gcc, I
get similar performance than what I get with Sun's JVM. If I remove the
array bounds check in the generated C file, I get something three times
faster, and close to what is achieved by a pure C implementation (and
the generated C file is actually very close to what a manual
implementation would do).
I got similar ratios with other algorithms (including non-crypto
algorithms).
I guess that the "10%" rule is more an evaluation of the time spent in
array bounds checking for a "complete typical application" (which is not
easy to define) but is not representative of what you get with a
single-task tool.
--Thomas Pornin
|
