Boost.Chain over at Github
Hi everyone, I just wanted to give a heads up to say that I'm actually now trying to get the Boost.Chain idea a little more weight by defining the interface of the type -- as you might remember, "chain" was pretty much the immutable string. I wanted to point those interested over to the Git repository and project page over on Github (https://github.com/mikhailberis/chain) and either watch the repository or submit pull requests if you fancy filling in some of the blanks there. At this time I'm pretty much stubbing out the implementation while trying to define a suitable interface from the start. The idea is that I would like to build this incrementally from the chains::builder type which will mostly do the linked data structure for doing a segmented string data type, and then a chains::chain which would act as a proxy. The chains::view (to be defined) will pretty much encapsulate an encoding tag (to determine the encoding/decoding policy/implementation statically) that will enable the encoded viewing of the data in the chain. The plumbing (which could very well be the more interesting part of the implementation) is still up in the air, but I'm thinking about doing an intrusive list of blocks, each block having metadata fields that indicate the size of the block (runtime defined, depending on the page size to ensure page-aligned addresses), a pointer to the block, and a reference count. I'm still thinking about making the reference count for the blocks be hosted in a block manager that maps the block's address to a reference count that's atomically incremented/decremented instead of making the reference count field be part of the actual block. Reason for this is so that touching the reference counts will not mark the page on which the actual data block is stored to be marked as "dirty", avoiding cache coherency issues on shared pages/cache-lines across multiple processors. Of course I may be getting ahead of myself here but if you're interested in helping define the interface at this time, please let me know and join the mailing list over at https://groups.google.com/group/boost-chain. Have a good one guys and I look forward to collaborating with those interested in building an immutable string data structure! -- Dean Michael Berris http://about.me/deanberris
Hi Dean, Dean Michael Berris wrote:
Hi everyone, I just wanted to give a heads up to say that I'm actually now trying to get the Boost.Chain idea a little more weight by defining the interface of the type -- as you might remember, "chain" was pretty much the immutable string. I wanted to point those interested over to the Git repository and project page over on Github (https://github.com/mikhailberis/chain) and either watch the repository or submit pull requests if you fancy filling in some of the blanks there.
I wonder, would it be a good idea to put together some sort of "string benchmark" suite? After all the previous discussion of string implementation styles, and the similar COW-or-not discussions in the XInt review, and considering the existing variations in string implementations between standard libraries, maybe it would be a good idea to try to quantify things? Perhaps this has already been done by someone? (Personally, although I use std::string a lot, it is almost never in an inner loop or other critical code.) Regards, Phil.
On Fri, Mar 18, 2011 at 5:33 AM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
Hi Dean,
Dean Michael Berris wrote:
Hi everyone, I just wanted to give a heads up to say that I'm actually now trying to get the Boost.Chain idea a little more weight by defining the interface of the type -- as you might remember, "chain" was pretty much the immutable string. I wanted to point those interested over to the Git repository and project page over on Github (https://github.com/mikhailberis/chain) and either watch the repository or submit pull requests if you fancy filling in some of the blanks there.
I wonder, would it be a good idea to put together some sort of "string benchmark" suite? After all the previous discussion of string implementation styles, and the similar COW-or-not discussions in the XInt review, and considering the existing variations in string implementations between standard libraries, maybe it would be a good idea to try to quantify things?
+1
Perhaps this has already been done by someone?
If it has been done, I definitely would like to use it. :)
(Personally, although I use std::string a lot, it is almost never in an inner loop or other critical code.)
That's fine, I deal with lots of network I/O as part of the HTTP implementation in cpp-netlib and it would be really good if I can step away from std::string from the internals to support larger strings without having to induce too much fragmentation when concatenating strings. The intention is to have suitably efficient (not necessarily optimal) string representations for code that need to deal with both small and potentially huge strings. Maybe if others would like to put the benchmark code under a Boost Software License and be pulled in from the chain project as a pull request, that would very much be welcome. Thanks Phil! -- Dean Michael Berris http://about.me/deanberris
On 18/03/2011 03:49, Dean Michael Berris wrote:
That's fine, I deal with lots of network I/O as part of the HTTP implementation in cpp-netlib and it would be really good if I can step away from std::string from the internals to support larger strings without having to induce too much fragmentation when concatenating strings. The intention is to have suitably efficient (not necessarily optimal) string representations for code that need to deal with both small and potentially huge strings.
Then you need a string which layout is compatible with the vectored I/O API provided by the system (readv/writev on POSIX, ReadFileScatter/WriteFileGather on Win32).
On Fri, Mar 18, 2011 at 6:37 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:
On 18/03/2011 03:49, Dean Michael Berris wrote:
That's fine, I deal with lots of network I/O as part of the HTTP implementation in cpp-netlib and it would be really good if I can step away from std::string from the internals to support larger strings without having to induce too much fragmentation when concatenating strings. The intention is to have suitably efficient (not necessarily optimal) string representations for code that need to deal with both small and potentially huge strings.
Then you need a string which layout is compatible with the vectored I/O API provided by the system (readv/writev on POSIX, ReadFileScatter/WriteFileGather on Win32).
Thanks Mathias, yes the data storage structure I'm looking to use will mostly obtained with either by mmap'ing an anonymous segment or through posix_malign(...) -- not sure of the Windows equivalent. The storage blocks would basically be chunks in memory, and I'm looking to make a chain a Boost.Asio compatible ConstBufferSequence. HTH -- Dean Michael Berris http://about.me/deanberris
Dean Michael Berris wrote:
On Fri, Mar 18, 2011 at 6:37 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:
On 18/03/2011 03:49, Dean Michael Berris wrote:
That's fine, I deal with lots of network I/O as part of the HTTP implementation in cpp-netlib and it would be really good if I can step away from std::string from the internals to support larger strings without having to induce too much fragmentation when concatenating strings. The intention is to have suitably efficient (not necessarily optimal) string representations for code that need to deal with both small and potentially huge strings.
Then you need a string which layout is compatible with the vectored I/O API provided by the system (readv/writev on POSIX, ReadFileScatter/WriteFileGather on Win32).
Thanks Mathias, yes the data storage structure I'm looking to use will mostly obtained with either by mmap'ing an anonymous segment or through posix_malign(...) -- not sure of the Windows equivalent. The storage blocks would basically be chunks in memory, and I'm looking to make a chain a Boost.Asio compatible ConstBufferSequence.
Hi, I would like to see the requirements for ConstBufferSequence be relaxed. In particular X::value_type --- T --- T meets the requirements for ConvertibleToConstBuffer. I would like it uses a model of ConstBuffer and Mutable Buffer instead of forcing a conversion to the specific class cont_buffer. The ContBuffer, Mutable requirements could be resumed to the ability to get the size and the (const/mutable) address either as member functions or as free functions. This relaxation on the requirements will avoid unneeded conversions. It seems to me that the user code will not inpact :). However the ASIO code will need to be changed in some places :( Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-Chain-over-at-Github-tp3384959p3389... Sent from the Boost - Dev mailing list archive at Nabble.com.
I think scatter/gather support is the only feature I've seen discussed that's not supported by std::rope (I only looked at GCC's, but it seems to support sharing of common substrings). And if you don't need fast concatenation (i.e. due to sharing), then you could use a const std::dequeue. So, unless I'm missing something, I think the question is pretty much down to the value of scatter/gather I/O. Now, I'm skeptical about the real-world benefits of scatter/gather I/O, over simply copying into a contiguous temporary buffer. It turns out GNU's libc will even do this automatically and transparently, if you exceed the I/O vector length limits of the kernel. RAM is just so much faster than even 10 Gig ethernet and SSDs. And since L3 cache is bigger than typical socket buffer sizes, you'll often find that emulating scatter/gather in userspace is essentially free. It wasn't always this way, but I'd argue that scatter/gather I/O something of an anachronism - it just isn't worth the trouble, any more. Does anyone know of any recent benchmarks on scatter/gather I/O? If I'm wrong, I'd like to know it. I did a quick search, but came up empty-handed. I saw something on LKML that seemed to compare it to a sequence of synchronous reads/writes to a file with O_SYNC, but I'm talking about replacing it with a copy + single read/write. I'm guessing you'd have to use a ramdisk for the difference to be measurable. Speaking of benchmarks, I ran across an old benchmark of GCC's std::string vs. STLport's std::string & std::rope. I don't know if the results are still relevant, but it has some string benchmarking code you could reuse (I think someone mentioned benchmarking it against other strings, earlier in the thread). http://complement.sourceforge.net/compare.pdf Matt ________________________________ From: boost-bounces@lists.boost.org on behalf of Mathias Gaunard Sent: Fri 3/18/2011 6:37 AM To: boost@lists.boost.org Subject: Re: [boost] Boost.Chain over at Github On 18/03/2011 03:49, Dean Michael Berris wrote:
That's fine, I deal with lots of network I/O as part of the HTTP implementation in cpp-netlib and it would be really good if I can step away from std::string from the internals to support larger strings without having to induce too much fragmentation when concatenating strings. The intention is to have suitably efficient (not necessarily optimal) string representations for code that need to deal with both small and potentially huge strings.
Then you need a string which layout is compatible with the vectored I/O API provided by the system (readv/writev on POSIX, ReadFileScatter/WriteFileGather on Win32). _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Mon, Mar 21, 2011 at 11:15 AM, Gruenke, Matt <mgruenke@tycoint.com> wrote:
I think scatter/gather support is the only feature I've seen discussed that's not supported by std::rope (I only looked at GCC's, but it seems to support sharing of common substrings). And if you don't need fast concatenation (i.e. due to sharing), then you could use a const std::dequeue. So, unless I'm missing something, I think the question is pretty much down to the value of scatter/gather I/O.
What would exactly mean for Chain to be S/G compatible? In my view the only requirement would be that the implementation allows the discovery of contiguous segments so that an io_vec or similar can be easily reconstructed (and this can be done very efficiently). Such an interface would be useful beyond scatter gather support (segmented algorithms, for example). If supporting S/G means that Chain should be layout compatible with io_vec, I think there is no advantage to that; consider a writev that returns with a partial write: now you would need to modify a probably const Chain to update the io_vec to finish the write (not only it would be ugly, but also thread unsafe); similar problem if you only want to write a subset of a Chain.
Now, I'm skeptical about the real-world benefits of scatter/gather I/O, over simply copying into a contiguous temporary buffer. It turns out GNU's libc will even do this automatically and transparently, if you exceed the I/O vector length limits of the kernel. RAM is just so much faster than even 10 Gig ethernet and SSDs. And since L3 cache is bigger than typical socket buffer sizes, you'll often find that emulating scatter/gather in userspace is essentially free. It wasn't always this way, but I'd argue that scatter/gather I/O something of an anachronism - it just isn't worth the trouble, any more.
In principle, if the implementation is capable of zero copy networking/Disk IO, there wouldn't need to be copied to kernel buffers. Another advantage is reduced peak memory usage which is very important if you need to serve many clients. Anyways, I do not know of any numbers. Supporting S/G might very well be a case of premature optimization. -- gpd
participants (6)
-
Dean Michael Berris -
Giovanni Piero Deretta -
Gruenke, Matt -
Mathias Gaunard -
Phil Endecott -
Vicente Botet