Writev

[Adam DePrince]

Often I've written code that generates some textual output and dumps
said output to a file or socket. Of course, we are all familiar with
the performance impact (multiple copies of text data and O(n**2)
performance) associated with the naive approach of:

string += "some other string"
string += "another string"

Many other programmers have faced a similar issue; cStringIO,
''.join([mydata]), map( file.write, [mydata]) are but some attempts at
making this process more efficient by jamming the components to be
written into a sequence.

These approaches have their drawbacks.

cStringIO and ''.join involve an extra copy of the string; map(
file.write ... potentially makes an excessive number of os write calls.
With the maturation of iterators in Python comes the consideration that
cStringIO and ''.join store the entire output in memory.
map(file.write, while allowing for the emission of data to a file or
socket while being generated, requires a lot of os calls. Even without
consideration for iterators, the elimination of the final concatenation
or drastic reduction in the number of os calls (context switches hurt)
could be a substantial benefit.

Perusing through the posix module reveals that the posix writev call is
not exposed. Writev is the POSIX answer to this problem for very
similar reasons. The ability to expose a list of strings to be
outputted to the hardware level would allow for the exploitation of some
rather sophisticated hardware. IIRC, some operating systems (BSD I
believe) have "zero copy" network code; it is conceivable that the final
concatenation of output could be entirely avoided given smart enough
drivers and hardware.

Of course, to take advantage of this requires that writev be exposed. I
have an implementation of writev. This implementation is reasonably
smart, it "unrolls" only so as many iteration.next calls as necessary to
fill the pointer list for the next invocation of writev. Of course, on
many systems (Linux, BSD) writev's limit is 1024 items, so to
accommodate users who don't want to peel off and hold in memory 1024
iteration.next( )'s, you can set an optional parameter to a smaller
value.

I'm not sure where to take this as a "next step." It seems too small a
change for a PEP. Any ideas?

You can download the patch from

http://deprince.net/software/writev/index.html

Adam DePrince

[Steven Bethard]

Re: Writev

Adam DePrince wrote:[color=blue]
> Many other programmers have faced a similar issue; cStringIO,
> ''.join([mydata]), map( file.write, [mydata]) are but some attempts at
> making this process more efficient by jamming the components to be
> written into a sequence.[/color]

I'm obviously misunderstandin g something because I can't figure out why
you would write:

map(file.write, [mydata])

instead of

file.write(myda ta)

Is your task to write a sequence/iterator of items into a file? I would
expect your example to look like:

map(file.write, mydata)

which I would write as:

file.writelines (mydata)

Could you explain a little more what your intent is here?

Steve

[Adam DePrince]

Re: Writev

On Mon, 2004-12-20 at 00:30, Steven Bethard wrote:[color=blue]
> Adam DePrince wrote:[color=green]
> > Many other programmers have faced a similar issue; cStringIO,
> > ''.join([mydata]), map( file.write, [mydata]) are but some attempts at
> > making this process more efficient by jamming the components to be
> > written into a sequence.[/color]
>
> I'm obviously misunderstandin g something because I can't figure out why
> you would write:
>
> map(file.write, [mydata])
>
> instead of
>
> file.write(myda ta)[/color]

No, you misunderstand. mydata is a metavariable symbolic for a long
list of things that would be in that list.

map( file.write, mydata ) where mydata is some really long list or
iterator.

[color=blue]
>
> Is your task to write a sequence/iterator of items into a file? I would
> expect your example to look like:
>
> map(file.write, mydata)
>
> which I would write as:
>
> file.writelines (mydata)
>
> Could you explain a little more what your intent is here?[/color]

file.writelines ( seq ) and map( file.write, seq ) are the same; the
former is syntactic sugar for the later.

Writev is a neat abstraction in posix that allows the operating system
to handle the gathering of data to be written instead of the application
just in-case something in the hardware is smart enough to support
scatter-gather I/O. With a dumb I/O device, either the user application
(write) or the OS (writev) has the chore of gathering the data to be
writen, concatenating it and sending it on its way. A lot of devices
are smart enough to be handled a list of pointers and lengths and be
told to "write this" to the device. In a sense, writev is a pretty
close approximation to the API provided by a lot of high end disk and
network controllers to the OS.

The benefit is that you don't have to choose between these two evils:

1) Copying your strings so they are all in a line
2) Context switching to your OS a lot.

Let us consider this straw man; the sequence that would be generated by:

def numbers():
for x in range( 10000000 ):
yield str( x )

You really don't want to say:

write( ''.join(), numbers )

Nor do you want to say:

map( write, numbers() )


Wouldn't it be nice to peal off the first 1000 items, tell the OS to
write them, peal off the next 1000 items, etc etc ... and not even have
to absorb the memcpy cost of putting them all together? Think of it as
the later, without quite as much harassment of the underlying operating
system.

Lastly, my intent is to expose the writev system call simply because:

* It is there.
* It is sometimes useful.
* If we get used to sharing our intent with the OS, the OS author might
get used to doing something useful with this knowledge.

Now you are probably thinking "but isn't this premature optimization."
Yeah, it is, which is why we are up to version 2.4 without it. But I
don't think it is premature anymore.

There is one more time that writev would be beneficial ... perhaps you
want to write a never ending sequence with a minimum of overhead?

def camera():
while 1:
yield extract_entropy ( grab_frame() )

open( "/tmp/entropy_daemon_ pipe", "w+" ).writev( camera(), 5 )
# 1/5 of the OS overhead, still get a fresh update every 5/30th of a
second, assuming 30 FPS








Adam DePrince

[Steven Bethard]

Re: Writev

Adam DePrince wrote:[color=blue]
> file.writelines ( seq ) and map( file.write, seq ) are the same; the
> former is syntactic sugar for the later.[/color]

Well, that's not exactly true. For one thing, map(file.write, seq)
returns a list of Nones, while file.writelines returns only the single
None that Python functions with no return statement do. More
substantially, file.writelines (as far as I can tell from the C code)
doesn't make any call to file.write.

I looked at fileobject.c and it looks like file.writelines makes a call
to 'fwrite' for each item in the iterable given. Your code, if I read
it right, makes a call to 'writev' for each item in the iterable.

I looked at the fwrite() and writev() docs and read your comments, but I
still couldn't quite figure out what makes 'writev' more efficient than
'fwrite' for the same size buffer... Mind trying to explain it to me again?
[color=blue]
> There is one more time that writev would be beneficial ... perhaps you
> want to write a never ending sequence with a minimum of overhead?
>
> def camera():
> while 1:
> yield extract_entropy ( grab_frame() )
>
> open( "/tmp/entropy_daemon_ pipe", "w+" ).writev( camera(), 5 )[/color]

I tried running:

py> def gen():
.... i = 1
.... while True:
.... yield '%i\n' % i
.... i *= 10
....
py> open('integers. txt', 'w').writelines (gen())

and, while (of course) it runs forever, I don't appear to get any memory
problems. I seem to be able to write fairly large integers too:

$ tail -n 1 integers.txt | wc
1 1 5001

How big do the items in the iterable need to be for writev to be necessary?

Steve

P.S. I certainly don't have anything against including your patch (not
that my opinion counts for anything) ;) but if it improves a common
file.writelines usage, I'd like to see it used there too when possible.

[Adam DePrince]

Re: Writev

On Mon, 2004-12-20 at 02:18, Steven Bethard wrote:[color=blue]
> Adam DePrince wrote:[color=green]
> > file.writelines ( seq ) and map( file.write, seq ) are the same; the
> > former is syntactic sugar for the later.[/color]
>
> Well, that's not exactly true. For one thing, map(file.write, seq)
> returns a list of Nones, while file.writelines returns only the single
> None that Python functions with no return statement do. More
> substantially, file.writelines (as far as I can tell from the C code)
> doesn't make any call to file.write.
>
> I looked at fileobject.c and it looks like file.writelines makes a call
> to 'fwrite' for each item in the iterable given. Your code, if I read
> it right, makes a call to 'writev' for each item in the iterable.[/color]

No, my code makes a call to writev for every nth iterable, where n is
usually 1024. Writev is the posix equivalent to writelines.
[color=blue]
>
> I looked at the fwrite() and writev() docs and read your comments, but I
> still couldn't quite figure out what makes 'writev' more efficient than
> 'fwrite' for the same size buffer... Mind trying to explain it to me again?[/color]


Okay. Imagine that you had a list of strings that you want to write to
a file.

You normally have two choices:

1. Copy all of the strings to a buffer and write that buffer.
2. Call write a lot

Remember that write and fwrite require a single buffer of data to
write. When you have a sequence, your items are not lined up one right
after the other in memory, so python or libc has to do a memcpy on each
element's contents to prepare it for a write. Every sequence element
will result in either a memcpy or a write. fwrite is special, it
buffers for you, converting scenario #2 to #1.

Writev gives you a third option. Rather than moving the data to one
place in preparation for the write, you can give the operating system a
list of where all of the bits are and it will get them for you.


[color=blue]
>[color=green]
> > There is one more time that writev would be beneficial ... perhaps you
> > want to write a never ending sequence with a minimum of overhead?
> >
> > def camera():
> > while 1:
> > yield extract_entropy ( grab_frame() )
> >
> > open( "/tmp/entropy_daemon_ pipe", "w+" ).writev( camera(), 5 )[/color]
>
> I tried running:
>
> py> def gen():
> ... i = 1
> ... while True:
> ... yield '%i\n' % i
> ... i *= 10
> ...
> py> open('integers. txt', 'w').writelines (gen())
>
> and, while (of course) it runs forever, I don't appear to get any memory
> problems. I seem to be able to write fairly large integers too:[/color]

Wrong example. Your example doesn't have memory problems, it has
efficency problems. Memory problems occur with:

''.join( list( gen()))
[color=blue]
>
> $ tail -n 1 integers.txt | wc
> 1 1 5001
>
> How big do the items in the iterable need to be for writev to be necessary?
>
> Steve
>
> P.S. I certainly don't have anything against including your patch (not
> that my opinion counts for anything) ;) but if it improves a common
> file.writelines usage, I'd like to see it used there too when possible.[/color]

I think you are looking at writev the wrong way. Notice that it is part
of posixmodule.c. You are tring to see why it is better to use from a
python perspective. I'm including it for the benefit of the underlying
operating system, not the python programmer.

writelines applies to a general Python file object. writev applies only
to C file descriptors. Writev can't replace writelines, after all it
makes no sense to cStringIO, gzip files for these are not valid C file
descriptors. Generally, writelines works fine.

Now why would you want to use writev? Optimization on the C side.

Understand that when you do file I/O you have to either:

a) Copy all of the strings to a new memory location
b) Call write over and over again

Sometimes, when you do b), userspace libraries (fwrite) will "optimize"
by buffering and doing a) for you. But you cannot escape the fact that
so long as your write parameter takes a single string for each
invocation, the underlying libraries are forced to choose between the
two options above.

Writev is the vector version of write. Whereas write accepts a single
pointer and length parameter, writev accepts a *list* of pointers and
size parameters. It represents a strategy c) -- just hand the list to
operating system

I want to include it because POSIX has a single OS call that
conceptually maps pretty closely to writelines. writev can be faster
because you don't have to do memory copies to buffer data in one place
for it -- the OS will do that, and can sometimes delegate that chore to
the underlying network or scsi card.

If you are still scratching your head, just think of writev as a C-file
descriptor only optimization of writelines that offloads the memory copy
cost of buffering to the OS in hopes that it can pass the buck to the
hardware (and IIRC, BSD does handle this correctly ... it has zero copy
network code, think about how cool it is to think that your network card
is going to traverse your list for you with a little help from the
writev function.)



Adam DePrince

[Steven Bethard]

Re: Writev

Adam DePrince wrote:
[snip great explanation][color=blue]
> I want to include it because POSIX has a single OS call that
> conceptually maps pretty closely to writelines. writev can be faster
> because you don't have to do memory copies to buffer data in one place
> for it -- the OS will do that, and can sometimes delegate that chore to
> the underlying network or scsi card.[/color]

Thanks that helped a lot!

Steve

[Mike Meyer]

Re: Writev

Adam DePrince <adam@cognitcor p.com> writes:
[color=blue]
> I want to include it because POSIX has a single OS call that
> conceptually maps pretty closely to writelines.[/color]

I just want to point out that on some systems, POSIX is a
compatability layer, not an OS layer. On those systems, the
implementer of writev is back at you choices a or b again.

I'm +0 on this idea.

<mike
--
Mike Meyer <mwm@mired.or g> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.