Thomas Pornin <pornin@[EMAIL PROTECTED]
> writes:
>According to Anton Ertl <anton@[EMAIL PROTECTED]
>:
>> That depends on the file system. However, I don't know how usual file
>> systems deal with non-linearly written files.
....
>For file systems with support for sparse files, consequences ranges from
>relatively benign (data chunks will be spread accross the disk, and you
>may have bad interactions with the read-ahead strategies of the kernel
>and the logic implemented by the disk itself, which both optimize the
>usual linear access pattern) to rather inconvenient (e.g. much more
>extra space used to describe the more complex file structure).
What file system are you thinking of? Even for extent-based file
systems, the worst case seems to be that they have to manage one
extent per page, which is not much extra space.
Concerning the bad interactions with read-ahead, we found that the
non-sequential access of demand-paging is not sped up as much as I had
expected by reading the accessed blocks in increasing order first; my
explanation for that was that the disk reads and caches whole tracks
(or at least those parts it encounters when searching for the correct
sector), and that read-ahead then helps some later demand-page access.
I would expect a similar effect to take place when the file system
places the file in non-sequential order, and the file is then written
in sequential order.
Hmm, that's worth an experiment:
I prepared a randomly written file as follows:
--------------------
use /space/blocks.fb
variable seed
: initiate-seed ( -- ) 74755 seed ! ;
: random ( -- n ) seed @[EMAIL PROTECTED]
1309 * 13849 + 262143 and dup seed ! ;
: benchblocks ( -- )
initiate-seed
100000 0 do
random block drop update save-buffers
loop ;
benchblocks
-----------------------
The file system is an Ext3 file system with 4KB block size, so writing
these 100000 Forth blocks resulted in a 224132KB file with an apparent
size of 262143KB. I also prepared a sequential file with 262143KB.
Then I umounted the file system and mounted it again to clear the
caches. Reading these files with cat took
real 8m3.171s for the randomly written file
real 0m10.290s for the sequentially written file
So, at least for Ext3 writing the file in random order results in a
file that is expensive to read sequentially; and the read-ahead of the
disk and the OS does not help much in this case (probably because the
file is so much larger than the disk cache (2MB), and the OS
read-ahead turns itself off when it sees random accesses); the disk is
a SAMSUNG SV1204H.
>> A compacting memory manager (GC or not) can be a good design for this
>> situation (it will fail even later, after even more thrashing:-), but
>> it's different from a copying collector.
>
>A mere terminology issue. I am talking about a memory manager which may
>move objects in memory, transparently from the application code point of
>view, and a compacting GC surely does that.
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?
>> In any case, that's not what you claimed earlier: you claimed that the
>> copying GC moves objects around to better fit the access patterns,
>> resulting in more cache-friendly behaviour by the program.
>
>Well, I claimed that, and then you claimed that it would not compensate
>the overhead of using the GC, which is why I began to state that the
>overhead is not big and may be zero, or even less. If the overhead is
>zero then whatever chache-related gain is obtained is a net gain.
And if we believe Appel, GC-managed memory is cheaper than
stack-managed memory.
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.
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?
>> Boy, Java takes a factor of 2-3 on array bound checks (after
>> optimization), when the typical numbers of the array bound checking
>> overhead I have read are 10% (and that's from papers on optimizing
>> them, which have every reason to inflate their significance).
>
>It is possible that Sun's JIT compiler does not perform a good job at
>optimizing array bounds checks,
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.
>Consequently, if array bounds checks can be optimized to have an
>overhead of only 10% (I have to trust your word on this)
It's only 10% to start with.
>then Java code
>can mechanically reach within 90% of compiled C code by the simple
>expedient of applying those optimization.
That assumes that array bounds checking is the only source of built-in
inefficiency (it isn't), and that there is no idiomatic inefficiency.
>> BTW, on such big machines a GC that rearranges data for the cache
>> would be even more beneficial. Does Sun's JVM use such a GC? I think
>> they would have made big PR about it if they did.
>
>As I said, Sun and the concept of PR have a rather uneasy relationship.
I did not hear you say it. And anyway, it's not true. One of the
UltraSPARCs (IIRC the UltraSPARC IIIi) had a new feature that would
help the branch prediction of interpreter dispatch. Technical details
were hard to find (a long time later I learned that this new
instruction pushed the predicted value on the return stack), but Sun
PR successfully touted it as an important Java acceleration feature.
They have also have a number of other PR successes (Java itself is
probably the biggest one), so I disagree with your statement.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2008:
http://www.complang.tuwien.ac.at/anton/euroforth/ef08.html
|
