seth:

-----Original Message----- From: libraries-bounces@haskell.org [mailto:libraries-bounces@haskell.org] On Behalf Of Bryan O'Sullivan Sent: Sunday, September 02, 2007 11:23 PM To: Peter Simons Cc: libraries@haskell.org Subject: Re: ByteString I/O Performance

Peter Simons wrote:

...

One way to get malloc() out of the picture would be to provide a variant of hGet that takes an existing, pre-allocated buffer as an argument, so that the user can allocate a ByteString once and re-use it for every single hGet and hPut.

This is already quite easy to do. See unsafeUseAsCStringLen in Data.ByteString.Base, and hGetBuf in System.IO.

Is it possible without resorting to an unsafeXXX function?

They're all 'unsafe' for different reasons :) The question should be: why is this unsafe? (It's unsafe because it doesn't copy the C string, so you need to have a side condition that the string isn't modified by C). -- Don

seth:

-----Original Message----- From: Donald Bruce Stewart [mailto:dons@cse.unsw.edu.au] Sent: Monday, September 03, 2007 12:03 AM To: Seth Kurtzberg Cc: libraries@haskell.org Subject: Re: ByteString I/O Performance

seth:

...

-----Original Message----- From: libraries-bounces@haskell.org [mailto:libraries-bounces@haskell.org]

On Behalf Of Bryan O'Sullivan

...

Sent: Sunday, September 02, 2007 11:23 PM To: Peter Simons Cc: libraries@haskell.org Subject: Re: ByteString I/O Performance

Peter Simons wrote:

...

One way to get malloc() out of the picture would be to provide a variant of hGet that takes an existing, pre-allocated buffer as an argument, so that the user can allocate a ByteString once and re-use it for every single hGet and hPut.

This is already quite easy to do. See unsafeUseAsCStringLen in Data.ByteString.Base, and hGetBuf in System.IO.

Is it possible without resorting to an unsafeXXX function?

They're all 'unsafe' for different reasons :) The question should be: why is this unsafe?

(It's unsafe because it doesn't copy the C string, so you need to have a side condition that the string isn't modified by C).

OK. Assume that I'm not doing any C coding, so that the only C code that is invoked is called from within the implementation (in this case the implementation of System.IO). Can I assume that no implementation code modifies the string? In other words, is it valid to assume that the side condition is never violated so long as I don't violate the side condition in my own C code (if any)?

Yes, that's right. Its safe as long as you don't modify the string yourself in C. -- Don

On Mon, Sep 03, 2007 at 07:11:45AM +0200, Tomasz Zielonka wrote:

On Mon, Sep 03, 2007 at 01:40:51AM +0200, Peter Simons wrote:

...

One way to get malloc() out of the picture would be to provide a variant of hGet that takes an existing, pre-allocated buffer as an argument, so that the user can allocate a ByteString once and re-use it for every single hGet and hPut.

This seems dangerous. For example, consider that the ByteString can be referenced by some lazy computation, expecting it to contain the data from some earlier hGet.

...

A different approach would be to try to reduce the cost for malloc() by using some sort of pre-allocated pool of ByteStrings behind the scenes.

I just wrote this, before I read you proposition: As safer alternative would be to keep a cache of pre-malloced buffers, populated by the ByteString finalizer. But the bookkeeping cost could outweight the benefit of avoiding malloc.

How are you getting these bytestrings? Normal bytestring allocation doesn't use malloc and doesn't use finalizers; it calls the (deceptively named) mallocForeignPtrBytes function, which allocates a block of data in the pinned GHC heap, nearly like any other Haskell object. Stefan

On Mon, 2007-09-03 at 01:40 +0200, Peter Simons wrote:

Donald Bruce Stewart writes:

...

It's been a while since I benchmarked the IO performance, so looks like time to revisit this issue.

Hi Bruce,

my impression is that performance cannot be improved significantly without providing a modified input API. For some purposes reading input in large chunks is fine, but for some purposes it is not. A network proxy server, for example, cannot afford to buffer large amounts of data for every connection. An I/O buffer size of, say 256KB, would be really not a good choice for such a program. Something like 4KB typically is, but the small buffer size means that large amounts of data will be read using a fairly large number of hGet calls. As it is, hGet performs at least one malloc() per read() call. That will be slow, no matter how optimized that code is.

One way to get malloc() out of the picture would be to provide a variant of hGet that takes an existing, pre-allocated buffer as an argument, so that the user can allocate a ByteString once and re-use it for every single hGet and hPut.

Stefan is right, the only place that C malloc() is used is in strict ByteString's hGetContents. Everywhere else we use GHC's pinned heap allocation. Strict ByteString ReadFile does not use hGetContents because in that case we know the file length, it uses hGetBuf. Also, createAndTrim does not do any copying when there is no trimming necessary, so in the best case we do only a single copy using hGetBuf. As I recall from when I profiled this for the ByteString paper, with a lazy ByteString implementation of unix 'cat' on disk files (rather than a network socket) we should only copy each chunk once (as far as I can see). The slowdown compared to a simple hGetBuf 'cat' was all down to cache locality, because we're cycling between a range of buffers rather than a single cache-hot buffer. The time overhead of memory allocation and GC is negligible. In the tests I did at the time I found that on fully cached files the slowdown compared to using a single mutable buffer was about 2-3x. I figured that overhead is not bad, considering it represents the worst case when no work is being done to transform the data in any way and we're not doing any real IO, just copying data from kernel memory to user space memory. If we're doing lots of short reads (like when reading from sockets) then there is an opportunity for improvement. We could read into an internal buffer and cut off as an immutable ByteString only the chunk that got filled. The remainder of the buffer could be used for the following reads until the whole buffer is exhausted and a new buffer has to be allocated. This is the buffering strategy we use in the binary library when serialising. Duncan

simons:

Duncan Coutts writes:

| As I recall from when I profiled this for the ByteString paper | [...], the slowdown compared to a simple hGetBuf 'cat' was all | down to cache locality, because we're cycling between a range | of buffers rather than a single cache-hot buffer.

I believe you are right. The following implementation performs just fine:

...

import System.IO import qualified Data.ByteString.Base as Str import qualified Data.ByteString as Str import Data.ByteString ( ByteString )

bufsize :: Int bufsize = 4 * 1024

hGet :: Handle -> ByteString -> IO ByteString hGet h buf = do i <- Str.unsafeUseAsCStringLen buf (\(p,n) -> hGetBuf h p n) return (Str.unsafeTake i buf)

catString :: Handle -> Handle -> IO () catString hIn hOut = Str.create bufsize (\_ -> return ()) >>= input where input buf = hGet hIn buf >>= output buf output buf b | Str.null b = return () | otherwise = Str.hPut hOut b >> input buf

main :: IO () main = do mapM_ (\h -> hSetBuffering h NoBuffering) [ stdin, stdout ] catString stdin stdout

time /bin/cat /dev/null

real 0m2.093s user 0m0.024s sys 0m2.068s

time ./cat-bytestring /dev/null

real 0m2.753s user 0m0.568s sys 0m2.184s

That's a useful benchmark. Thanks for looking into this. -- Don

On Tue, 2007-09-04 at 20:07 +0200, Peter Simons wrote:

Donald Bruce Stewart writes:

...

...

hGet :: Handle -> ByteString -> IO ByteString hGet h buf = do i <- Str.unsafeUseAsCStringLen buf (\(p,n) -> hGetBuf h p n) return (Str.unsafeTake i buf)

That's a useful benchmark. Thanks for looking into this.

It was a pleasure. How do you feel about providing this kind of input API to the user as part of the module?

We can't provide this interface as it modifies the immutable input ByteString. What you're looking for is to copy into a mutable buffer. That buffer cannot be itself a ByteString as they're immutable. The best we can do is to copy into a newly allocated buffer as we do in hGet. In the best case we can do this with a single copy. We could look at the trimming again if that's an issue. So if you want an api that provides a mutable input buffer, you'll need something other than a ByteString. We do have something like this in the binary package, which we've been considering cleaning up and bringing into the bytestring package. However even that doesn't give you a mutable buffer that you'd want for fast 'cat', that really requires an api that guarantees that the buffer is no longer in use when the next chunk is read, destroying the previous content of the buffer.

By the way, did you receive my e-mail about the race condition in readFile?

Yes, it's a good point. We could fix it my doing more reads in the same style a hGetContents. Duncan

Peter Simons wrote:

Duncan Coutts writes:

...

We can't provide this interface as it modifies the immutable input ByteString.

Well, one could call it unsafeHGet. :-)

...

[Mutable input buffer] really requires an api that guarantees that the buffer is no longer in use when the next chunk is read, destroying the previous content of the buffer.

I see your point. It would be nice if the API would guarantee that the ByteString cannot be misused. Personally, I feel that is a minor point though.

Remember that Haskell expressions are evaluated lazily, that's why we have the IO monad for doing input/output. Hence, mutable values that look like pure ones become unpredictable and are considered a major sin in Haskell land, please don't do it. As catBuf crucially depends on the mutability of the buffer, ByteStrings are not the right data structure to use in that case, that's all there is to it. Regards, apfelmus

Peter Simons wrote:

...

Hence, mutable values that look like pure ones become unpredictable and are considered a major sin in Haskell land, please don't do it.

It feels patronizing to tell someone else what he should or shouldn't do. What can I say? Outside of Haskell land there are people who believe that software should, like, work, instead of falling apart whenever you feed it input data larger than a few kilobytes and to reach that objective those people are absolutely prepared to face the wild unpredictability of -- *gasp* -- pointers!

I didn't intend to patronize, I apologize for the harsh words. It's just that there's a difference between manipulating pointers peek :: Ptr Word8 -> IO Word8 -- :) poke :: Word8 -> Ptr Word8 -> IO () and breaking language semantics peek :: Ptr Word8 -> Word8 -- :( poke :: Word8 -> Ptr Word8 -> ()

...

As catBuf crucially depends on the mutability of the buffer, ByteStrings are not the right data structure to use in that case, that's all there is to it.

A ByteString is a pointer, a byte size, and a byte offset. As such, it is the perfect data structure for a program like catBuf.

Not quite. ByteStrings are intended to be a memory-efficient representation of Strings and the memory efficiency is implemented in Haskell with buffers and unsafePeformIO. But great care is taken to preserve language semantics in the exported API which means that ByteStrings have to be immutable. Note that the copy function is not for assuring immutability but for handling possible space leaks. Regards, apfelmus

On Wed, 2007-09-05 at 21:30 +0200, Peter Simons wrote:

As far as I can tell, the only reason why a function like 'unsafeUseAsCStringLen' has to be dubbed unsafe is because 'index' makes it unsafe. The limitation that ByteString has to be immutable is a consequence of the choice to provide 'index' as a pure function.

Well, it's not just index, all the functions that get data from the ByteString, like head/tail/uncons etc etc are pure. That is the whole point of the design of ByteString, to provide pure/immutable high performance strings. What you want is just fine, but it's a mutable interface not a pure one. We cannot provide any operations that mutate an existing ByteString without breaking the semantics of all the pure operations. It's very much like the difference between the MArray and IArray classes, for mutable and immutable arrays. One provides index in a monad, the other is pure.

Personally, I won't use 'index' in my code. I'll happily dereference the pointer in the IO monad, because I've found that to be no effort whatsoever. I love monads. For my purposes, 'unsafeUseAsCStringLen' is a perfectly safe function. The efficient variant of 'hGet' I posted can be implemented on top of it, so that 'hGet' is by all means a safe function in my code. There really is no risk at all, unless one uses 'index' or something that's based on it.

Right, or if you were to hand out a ByteString and then change the contents of it when nobody is looking then that's very much unsafe. So the point is you can break the semantics locally and nobody will notice. It's not a technique we should encourage however.

The way I see it, there will be other people who'll find the performance limitations of standard 'hGet' a decisive factor in their design decisions. Chances are, those people will wonder about using the base pointer for hGetBuf and then they'll end up re-inventing the wheel we just came up with.

I'd rather not provide a quick easy way to break the semantics. unsafeUseAsCStringLen and friends are already plenty enough rope...

Maybe I'll find the time to submit a patch to the documentation, so that fine points like an optimal buffer size etc. are explained in more detail than they are right now. It would be nice if some kind of result would come out of this discussion.

I really don't think we can provide anything that copies into an existing pre-allocated ByteString. As far as I can see, the best we can do is to allocate a fresh buffer and do a single copy into that. Mutating an existing buffer is fine, and System.IO already provides hGetBuf. But you have to be really really careful if you create a ByteString based on the contents of that mutable buffer, without making any copy first.

Anyway, thank you. I appreciate everyone's efforts in helping me figure out why I/O with ByteString is more than two times slower than it could be.

Thanks very much for pointing out where we are copying more than necessary. As for the last bit of performance difference due to the cache benefits of reusing a mutable buffer rather than allocating and GCing a range of buffer, I can't see any way within the existing design how we can achieve that. Bear in mind, that these cache benefits are fairly small in real benchmarks as opposed to 'cat' on fully cached files. Usually you do some actual IO and some operation on the data rather than just copying it from one file descriptor to another. For example, my lazy bytestring binding to iconv performs exactly the same as the command line iconv. In that case we are doing a bit of work on the data which swamps the cache benefits that the command line iconv prog gets from using mutable buffers. If we are trying to optimise the 'cat' case however, eg for network servers, there are even lower level things we can do so that no copies of the data have to be made at all. eg mmap or linux's copyfile or splice. ByteString certainly isn't the right abstraction for that though. Duncan

On 06 Sep 2007 02:30:28 +0200, Peter Simons wrote:

Duncan Coutts writes:

...

What you want is just fine, but it's a mutable interface not a pure one. We cannot provide any operations that mutate an existing ByteString without breaking the semantics of all the pure operations.

Is that so? How exactly does mutating a ByteString break the semantics of the pure function 'take'?

Because if you mutate the original bytestring the value of the other bytestring (returned from 'take') will change. Not pure. Bad. Evil. Etc.

...

It's very much like the difference between the MArray and IArray classes, for mutable and immutable arrays. One provides index in a monad, the other is pure.

Right. Now I wonder: why does ByteString provide an immutable interface but not a mutable one? Apparently mutable interfaces are useful for some purposes, right? Why else would the Array package provide one?

It doesn't provide two different interfaces to the same data structure, it provides two different data structures. You can't have a pure interface AND an impure one, as the impure one could then mutate values that are used with the pure interface, which would mean that the pure interface is broken (see above).

...

Bear in mind, that these cache benefits are fairly small in real benchmarks as opposed to 'cat' on fully cached files.

Do I understand that right? It sounds as if you were saying that -- in the general case -- allocating a new buffer for every single read() is not significantly slower than re-using the same buffer every time. Is that what you meant to say?

I think he said that most of the speed difference is due to better cache performance when reusing the same buffer, but in general you do "other stuff" as well which won't be as benign for the cache and the difference will be smaller (if at all noticable).

...

ByteString certainly isn't the right abstraction for that though.

I am sorry, but that is nonsense. A ByteString is a tuple consisting of a pointer into raw memory, an integer signifying the size of the front gap, and an integer signifying the length of the payload. That data structure is near perfect for performing efficient I/O. To say that this abstraction isn't right for the task is absurd. What you mean to say is that you don't _intend_ it to be used that way, which is an altogether different thing.

A ByteString is an immutable data structure representing a string, if you need a mutable one then it's not the right abstraction *by definition*. Yes, a ByteString is not intended to be a mutable buffer, which is precisely what makes it not the right abstraction if you need that (not an "altogether different thing", it is THE thing). The fact that the internal representation would look similar to a different abstraction which did allow mutation doesn't mean that *this* abstraction is the right choice. This is analogous to Java, and C# - if you need a mutable string buffer the "string" class is not the right abstraction, you use the string builder classes. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862

Bryan O'Sullivan writes:

I understand from your earlier admission that you have been having some bad days recently, and I look forward to you kindly not sharing the fruits of said bad days with the list.

Bryan, my mood would be a lot better if you would address my technical points on this list instead of my mood. I realize this discussion is going nowhere. It's hard for me to understand how people manage to say things like "you can't do that" despite the fact that I posted code which does exactly that, but I guess I don't have to understand everything. Take care everyone, Peter

bos:

It is perfectly true that you can take an existing ByteString and smoosh its innards however you like, because the authors sensibly made this possible. However, doing so breaks referential transparency, so it's not encouraged as a general principle. The fact that a ByteString has a pointer to a nice flat piece of memory inside is an implementation detail, and doesn't change the fact that it's intended to be immutable.

If you personally know for sure that you're not going to accidentally screw yourself by running a lazy computation on a ByteString that you then modify while the computation is still thunked, then by all means, go to town. But any claim that this is generally a safe thing to do would be completely wrong. It's very much in the realm of "here's the gun, there's your foot, be careful".

Perhaps Peter just wishes to define a newtype MutableByteString type for mutable use, with much the same representation as the existing immutable ByteString, but without the purity guarantees and with all operations in IO? -- Don

Peter Simons wrote:

Is that so? How exactly does mutating a ByteString break the semantics of the pure function 'take'?

http://www.sgi.com/tech/stl/Rope.html That's roughly the same in a "practical" language. Please read and understand it completely before responding.

A ByteString is a tuple consisting of a pointer into raw memory, an integer signifying the size of the front gap, and an integer signifying the length of the payload.

No, it's not. You're confusing abstract data types and their representation. If you want to work with a tuple of a pointer and two integers, by all means use a tuple of a pointer and two integers. -Udo