What happened to Double Buffering?
Roedy Green
that read a large CSV file [System.out.print(".")] I was quite
surprised to discover I could easily see the pause when it read the
next buffer full -- synched with the disk light. (Maybe I err. Maybe I
was seeing GCs).
Way way back in the olden days when computers had about 16K and you
coded in assembler, we did double buffering. In other words, when you
were reading a sequential file, you processed one buffer while the i/o
hardware was filling the other. This was the NORMAL way of doing
things. Later, double buffering was built in to COBOL. You got it by
default without writing any code.
Today, when we have RAM coming out our ears we have reverted back to
SINGLE buffering. We alternate between processing and waiting for I/O
on the same buffer.
What is the matter with us? It is as though we imagine we still have a
single threaded DOS OS.
--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
Daniel Pitts
which is what you seem to be describing.
As for caching/buffering that you suggest, it is usually handled at the
OS level, rather than at the app level. You can add additional
buffering by using BufferedInputStream. Also, depending on your
application, if you really need that big of a speed increase, decide to
read the whole thing into memory up front.
Alternately, if you want to read ahead, you can create your own
multi-threaded system to do so.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
Roedy Green
<newsgroup....@virtualinfinity.net> wrote, quoted or indirectly
quoted someone who said :
>Double Buffering generally refers to rendering, not look-ahead caching,
>which is what you seem to be describing.
The use of the term "double buffering" for lookahead i/o goes back to
the 1960s. Back then the closest you had to rendering was vector
display hardware, where a cathode ray beam traced out an image,
looking like star constellation map.
The buffering you get in BufferedInputStreams uses a single buffer.
That means your thread blocks to do i/o when the buffer empties.
With double buffering rendering, you write to a buffer in RAM.
Periodically, it gets copied to the physical REGEN hardware. If the
copy were done by a video processor, your task would have to block for
this process, analogously to the way disk i/o single buffering works..
If the copy were done by the CPU, your task would not block. It would
simple busy itself with the copy.
Roedy Green
<see_w...@mindprod.com.invalid> wrote, quoted or indirectly quoted
someone who said :
>Today, when we have RAM coming out our ears we have reverted back to
>SINGLE buffering. We alternate between processing and waiting for I/O
>on the same buffer.
I will offer this hypothesis. Double buffering requires multitasking.
This is perceived as complicated, and hence was left out of early
personal OSes such as CPM where you might have had only 4 to 64K to
play with.
In the 1940s to circa1970 , computers primarily did batch processing
and worked on one problem at a time. Hence the elapsed time for batch
processing was very important. Double buffering helps this.
Later with mainframes, you had several batch jobs running at once.
Here the computer could work on some other job while a batch job was
blocked on i/o. Double buffering became less important.
Today with desktops there is little sequential batch processing.
Double buffering is for sequential batch processing. Unlike COBOL, C
and Java don't have the notion built in. Even if the OS offered it, it
would take a while for it to become supported again.
In my world, I tend to read/write entire files in one i/o operation..
Double buffering could not beat that.
The reason may be that sequential batch processing is now considered a
niche application.
The Ghost In The Machine
<see_w...@mindprod.com.invalid>
wrote
on Tue, 24 Jun 2008 09:53:25 GMT
<8fg1649pur9gbvnrs...@4ax.com>:
> On Mon, 23 Jun 2008 01:54:08 GMT, Roedy Green
> <see_w...@mindprod.com.invalid> wrote, quoted or indirectly quoted
> someone who said :
>
>>Today, when we have RAM coming out our ears we have reverted back to
>>SINGLE buffering. We alternate between processing and waiting for I/O
>>on the same buffer.
>
> I will offer this hypothesis. Double buffering requires multitasking.
> This is perceived as complicated,
It *is* complicated. Multitasking among other things
requires lock synchronization, so that two tasks sharing
a resource don't clobber it.
One of the more interesting disciplines that got left
behind was the notion of coroutines as well. (That's
probably a side issue in this particular thread.)
> and hence was left out of early
> personal OSes such as CPM where you might have had only 4 to 64K to
> play with.
>
> In the 1940s to circa1970 , computers primarily did batch processing
> and worked on one problem at a time. Hence the elapsed time for batch
> processing was very important. Double buffering helps this.
And was relatively simple to set up, if one had access to
the interrupt vectors directly.
>
> Later with mainframes, you had several batch jobs running at once.
> Here the computer could work on some other job while a batch job was
> blocked on i/o. Double buffering became less important.
>
> Today with desktops there is little sequential batch processing.
> Double buffering is for sequential batch processing. Unlike COBOL, C
> and Java don't have the notion built in. Even if the OS offered it, it
> would take a while for it to become supported again.
>
> In my world, I tend to read/write entire files in one i/o operation..
> Double buffering could not beat that.
I can do one better, though I rarely bother (I've seen
it done by a co-worker though); one can set up a virtual
memory area that is associated with a file, and then access
the area using char* pointers. The file load in this case
is done on an incremental basis, with pages faulting in as
needed. (mmap()/mmap2(), mremap(), munmap().)
Java does support this concept as of 1.5 or so; I've not
tried it though.
>
> The reason may be that sequential batch processing is now considered a
> niche application.
>
--
#191, ewi...@earthlink.net
Linux. Because it's there and it works.
Windows. It's there, but does it work?
** Posted from http://www.teranews.com **
Daniel Pitts
Just wrote this on my commute today. Only partially tested, and not
tested for speed.
If you're interested, I'd like to see a benchmark between a standard
InputStream, and this DoubleBufferedInputStream in your CSV application.
--- Start DoubleBufferedInputStream.java ---
/*
This code is being released into the public domain. My only request
is that you leave the @author attribution intact. Adding new
attributions is fine.
It is distributed for use as-is. If there is a problem with it, feel
free to correct.
If you need help correcting it, feel free to seek that from someone
who is willing to help.
Also, feel free to contribute any improvement to the public domain.
Donations also welcome. Check at virtualinfinity.net for contact
info.
*/
package net.virtualinfinity.io;
import java.io.InputStream;
import java.io.IOException;
import java.util.concurrent.locks.*;
/**
* A <code>DoubleBufferedInputStream</code> will buffer a wrapped input
* stream in a separate thread, so that reading can be done concurrently
* with processing. The supplied InputStream must be safe to be
* accessed from a single thread other than the one that created the
* DoubleBufferedInputStream object. Note that this implementation does
* NOT support mark/reset. If you need that functionality, wrap the
* stream with a java.io.BufferedInputStream.
*
* There has been no attempt to make this class thread-safe, other than
* what is necessary to handle the read-ahead behaviour.
*
* @author Daniel Pitts
* @version 1.0, 06/23/2008
*/
public class DoubleBufferedInputStream extends InputStream {
private final static int defaultBufferSize = 4096;
/**
* Represents one buffer. In practice, two buffers per
* DoubleBufferedInputStream instance can exist at one time, the
* "previously read" buffer, and the "in the process of reading".
*/
private static class Buffer extends InputStream {
private final byte[] data;
private int count;
private int position;
private boolean endOfStream;
private IOException exception;
public Buffer(int bufferSize) {
data = new byte[bufferSize];
}
/**
* Attempts to fill this buffer with data from in. If EOS is
* reached or an exception encountered. These facts are recorded
* for later.
* @param in the stream to fill from.
*/
public void fill(InputStream in) {
assert !doneFilling() : "Fill called when done filling!";
try {
int read = in.read(data, count, data.length - count);
if (read == -1) {
endOfStream = true;
} else {
count += read;
}
} catch (IOException e) {
exception = e;
}
}
/**
* Test if fill should be called again.
* @return false if fill can safely and usefully be called
* again.
*/
public boolean doneFilling() {
return count == data.length ||
endOfStream ||
exception != null;
}
/**
* Test if the meaningful data in this buffer has been depleted.
* @return true if a new buffer should be retrieved.
*/
public boolean depleted() {
return !lastBuffer() && position >= count;
}
@Override
public int read() throws IOException {
if (checkEndOfBuffer()) return -1;
return data[position++];
}
@Override
public int read(byte[] b, int off, int len) throws IOException {
if (checkEndOfBuffer()) return -1;
final int toCopy = Math.min(available(), len);
System.arraycopy(data, position, b, off, toCopy);
position += toCopy;
return toCopy;
}
/**
* Check for end-of-buffer conditions and handle appropriately.
* @return true if were at the end of the stream.
* @throws IOException at end of buffer when an exception
* occurs during fill()
* @throws IllegalStateException when end of buffer is reached
* and no other state is indicated.
*/
private boolean checkEndOfBuffer() throws IOException {
if (position >= count) {
if (exception != null) {
throw exception;
}
if (endOfStream) {
return true;
}
throw new IllegalStateException("Buffer depleted.");
}
return false;
}
/**
* @return false if there could be more buffers to follow.
*/
private boolean lastBuffer() {
return endOfStream || exception != null;
}
@Override
public int available() {
return count - position;
}
}
// The current buffer, or null if not yet filled. Access guarded by
// bufferLock.
private Buffer buffer;
// Flag to short-circuit the filling routine and return with any
// available bytes. Write access guarded by bufferLock.
private volatile boolean waitingForBuffer;
// Flag to indicate stream is closed.
private volatile boolean closed;
// Lock to guard buffer.
private final Lock bufferLock = new ReentrantLock();
// Condition waiting for the predicate that buffer is not null.
private final Condition bufferSet = bufferLock.newCondition();
// Condition waiting for the predicate that buffer is null.
private final Condition bufferEmpty = bufferLock.newCondition();
// The maximum buffer size.
private final int bufferSize;
// The wrapped input stream.
private InputStream in;
// The thread that will read a buffer.
private final Thread bufferReader = new Thread() {
public void run() {
Buffer buffer;
do {
buffer = new Buffer(bufferSize);
do {
buffer.fill(in);
} while (!buffer.doneFilling() && !waitingForBuffer);
putBuffer(buffer);
} while (!buffer.lastBuffer() && !closed);
}
};
/**
* Waits for the current buffer to be empty, and the new buffer.
* @param nextBuffer the new buffer.
*/
private void putBuffer(Buffer nextBuffer) {
bufferLock.lock();
try {
while (buffer != null) {
bufferEmpty.awaitUninterruptibly();
}
buffer = nextBuffer;
waitingForBuffer = false;
bufferSet.signalAll();
} finally{
bufferLock.unlock();
}
}
/**
* Creates a <code>DoubleBufferedInputStream</code>
* and saves its argument, the input stream
* <code>in</code>, for later use.
*
* @param in the underlying input stream.
*/
public DoubleBufferedInputStream(InputStream in) {
this (in, defaultBufferSize);
}
/**
* <code>DoubleBufferedInputStream</code> and saves its argument,
* the input stream <code>in</code>, for later use. Sets the
* maximum size of each buffer. Note that there can be two buffers, so
* the amount of memory used is at least 2*bufferSize.
* @param in the underlying input stream.
* @param bufferSize the size for each buffer.
*/
public DoubleBufferedInputStream(InputStream in, int bufferSize) {
this.bufferSize = bufferSize;
this.in = in;
}
/**
* Check to make sure stream is not close, and then get the next
* available buffer.
* @return the available buffer.
* @throws IOException if the stream is closed, or the current
* thread is interrupted.
*/
private Buffer getBufferIfOpen() throws IOException {
if (closed) {
throw new IOException("Stream closed");
}
bufferLock.lock();
try {
startReaderIfNecessary();
emptyDepletedBuffer();
makeBufferAvailable();
return buffer;
} finally {
bufferLock.unlock();
}
}
/**
* Make sure that the current buffer is available, asking the
* reader thread to short-curcuit its work if necessary.
*
* A call to this method must be guarded by bufferLock.
* @throws IOException if the current thread is interrupted while
* waiting.
*/
private void makeBufferAvailable() throws IOException {
while (buffer == null) {
waitingForBuffer = true;
try {
bufferSet.await();
} catch (InterruptedException e) {
throw
new IOException("Interrupted while waiting for buffer.",
e);
}
}
}
/**
* Ensure that the bufferReader thread has actually been started.
* If it hasn't been started, this method pre-fills one buffer
* before starting the reader.
*
* A call to this method must be guarded by bufferLock.
*/
private void startReaderIfNecessary() {
if (bufferReader.getState() == Thread.State.NEW) {
buffer = new Buffer(bufferSize);
buffer.fill(in);
bufferReader.start();
}
}
/**
* Empty a buffer if it has been depleted.
*
* A call to this method must be guarded by bufferLock.
*/
private void emptyDepletedBuffer() {
if (buffer != null && buffer.depleted()) {
buffer = null;
bufferEmpty.signalAll();
}
}
@Override
public int read() throws IOException {
int result = getBufferIfOpen().read();
cleanBuffer();
return result;
}
/**
* Convenience method that cleans up a depleted buffer.
*/
private void cleanBuffer() {
bufferLock.lock();
try {
emptyDepletedBuffer();
} finally{
bufferLock.unlock();
}
}
@Override
public int read(byte b[], int off, int len) throws IOException {
int result = getBufferIfOpen().read(b, off, len);
cleanBuffer();
return result;
}
@Override
public int available() throws IOException {
if (bufferLock.tryLock()) {
try {
if (buffer != null) {
return buffer.available();
}
} finally{
bufferLock.unlock();
}
}
return 0;
}
@Override
public void close() throws IOException {
closed = true;
in.close();
}
}
--- End DoubleBufferedInputStream.java ---
Tim Smith
Roedy Green <see_w...@mindprod.com.invalid> wrote:
> Today, when we have RAM coming out our ears we have reverted back to
> SINGLE buffering. We alternate between processing and waiting for I/O
> on the same buffer.
>
> What is the matter with us? It is as though we imagine we still have a
> single threaded DOS OS.
Nothing is the matter with us. CPUs got faster. That's what it sounds
like you are seeing.
Let's say there are two buffers, so while the application is processing
one, the I/O system is filling the other. Your timeline would then be
something like this:
I/O System Application
---------- -----------
Request data, wait for response
start filling buffer #1 ...
... ...
... ...
... ...
... ...
... ...
... ...
... ...
finish filling buffer #1 ...
give buffer #1 to app ...
start filling buffer #2 start processing buffer #1
... finish processing buffer #1
... update progress bar
... request data, wait for response
... ...
... ...
... ...
... ...
finish filling buffer #2 ...
give buffer #2 to app ...
start filling buffer #1 start processing buffer #2
... finish processing buffer #2
... update progress bar
... request data, wait for response
... ...
... ...
... ...
... ...
finish filling buffer #1 ...
give buffer #1 to app ...
start filling buffer #2 start processing buffer #1
The app pauses because the app can consume data much faster than the
disk can provide it.
--
--Tim Smith
Lew
> I can do one better, though I rarely bother (I've seen
> it done by a co-worker though); one can set up a virtual
> memory area that is associated with a file, and then access
> the area using char* pointers. The file load in this case
> is done on an incremental basis, with pages faulting in as
> needed. (mmap()/mmap2(), mremap(), munmap().)
>
> Java does support this concept as of 1.5 or so; I've not
> tried it though.
Are you referring to MappedByteBuffer? That was introduced in the now
obsolescent version 1.4 of Java. It's hardly new.
--
Lew
Roedy Green
<ew...@sirius.tg00suus7038.net> wrote, quoted or indirectly quoted
someone who said :
>I can do one better, though I rarely bother (I've seen
>it done by a co-worker though); one can set up a virtual
>memory area that is associated with a file, and then access
>the area using char* pointers. The file load in this case
>is done on an incremental basis, with pages faulting in as
>needed. (mmap()/mmap2(), mremap(), munmap().)
that would do well if you were processing only part of the file, but
if you were processing every byte, then one giant i/o to read the whol
thing would do better. Otherwise you could get a physical I/O per 2K
or so, not even as good as a BufferedReader.
The Ghost In The Machine
<see_w...@mindprod.com.invalid>
wrote
<146j64hrfa5evrkgm...@4ax.com>:
I'd frankly have to look, and it may depend on OS. Apart
from an optimization thing (if one open()s the file the OS
might assume readahead; mmap() might cause the OS to assume
entirely random), I don't see that much of a difference,
from a pure performance standpoint.
Then again, I've not done benchmarks.
Three other drawbacks, all roughly based on the system
I'm using internally (a template C++ affair):
[1] If one stores data structures in a file using mmap(),
one is obliged to ensure that the pointer returned by
mmap() is properly processed. In particular, if mmap()
returns a different pointer the structures won't work if
simple pointers are used. Two workarounds are possible:
offsets and self-relative pointers. Both are flawed.
A third solution would require a prepass and is rather
ugly; the old pointer is stored somewhere in the file and
all known pointers adjusted upon initial load.
[2] The workarounds in [1] extract additional processor
time; either one has to add to a base, or subtract two
pointers, when doing a dereference. Since one is "reading"
from a file anyway, this may not be a serious issue.
[3] The structures are by necessity processor-specific.
If a file is saved on an mk680x0 and loaded by an ix86,
conversion needs to happen. ASCII I/O doesn't have this
problem (though it has other issues).
--
#191, ewi...@earthlink.net
Conventional memory has to be one of the most UNconventional
architectures I've seen in a computer system.