January 2011 - Boost - lists.boost.org

Re: [boost] [string] proposal
by Brent Spillner 29 Jan '11

29 Jan '11

On Jan 29, 2011, at 8:43 AM, David Bergman wrote: >There are four layers in play here: >1. The sequence of characters/symbols, as in CS string; totally abstract but precise... (one such CS string can be represented as Unicode or Latin-1 at #2, for instance.) >2. The sequence of code points, in a given character set. Yes, one CS string (as in #1) can have multiple distinct manifestations at this level. They could be identical in >integral sequences. >3. The sequence of code values, using an encoding form such as UTF-8 or UTF-16 for a Unicode code point. >4. The byte storage representing the code values; could be a contiguous sequence of bytes or chunks, etc. Which, IMHO, is exactly why it's (past) time to radically rethink the standard string interface. Your four layers share the properties that: (a) They can all be physically represented within the same data structure (i.e. layer #4), and (b) For any layer, there already exists a lot of legacy code that conceptualizes passed-in strings at that layer and that makes corresponding assumptions. To me, these facts imply that a 'view'-based approach is the right way to go. Furthermore, views should not be concrete data structures themselves, but simply iterator pairs (ranges) that internally point to some arbitrary data structure, and externally present a model of a linear sequence of atomic characters/codepoints/etc. In software development Nirvana, APIs and algorithms will operate on iterator_ranges at the appropriate conceptual level, rather than intruding into the underlying data structures, and at the interfaces with reality we'll just copy data to and from more concrete representations using the chosen encoding. Some of those interfaces (with low-level device drivers or with memory-mapped hardware itself) might never go away, but many (e.g. a GUI API that accepts a string and returns a texture of its glyphs) would hopefully eventually migrate to the iterator model. For example, one might write std::string underlying_data = obtain_validated_data_from(somewhere); text<ucs4, codept_view, decltype(underlying_data)> codepoints(assume_utf8(underlying_data)); text<utf8, char_view, decltype(underlying_data)> characters(assume_utf8(underlying_data)); if (codepoints.length() > characters.length()) contains_multipoint_characters = true; // converse not necessarily true if there are codepoints for multi-character ligatures const char *byteptr = linear_representation(underlying_data); // may or may not accurately track later changes, especially if the underlying data is non-contiguous, but that's really a usage protocol question and not for the data structure to solve--- anyway, strdup() if you want a snapshot from a given point in time text<utf8, char_view, characters::internal_representation> substring = all_after(characters.begin(), characters.end(), "phrase to match"); std::vector<wide_char_t> char_array; std::copy(substring.begin(), substring.end(), char_array.begin()); etc. When you think your usage pattern favors a rope or a chain over a std::string, you only have to change the declaration of the underlying_data object and the rest works seamlessly. I think Dean favors immutability because that makes it easy for the iterator-adaptors to cache data in the representation they need (or in more local storage in a NUMA environment), but like specifying a particular byte encoding for the underlying data this would be more for convenience and performance optimization than a firm requirement. When the underlying representation is a mutable type, read-only view adapters are still free to cache chunks of data as long as they check for a fingerprint that writable view adapters leave on the underlying structure whenever they commit a change. Consider the underlying data structure as a sequence of arbitrary 'tokens' (bytes, characters, codepoints, variable-length compressed bitstrings... whatever makes sense); a read-only substring cache that depends on tokens i though j (inclusive) of version v of the underlying representation can be described by the tuple r(v, i, j), while a serialized write operation that changes the tokens in positions i though j from version v to version v+1 can be described by the tuple w(v+1, i, j). A write w(v, x, y) invalidates all or part of a read cache r(v', x', y') if and only if v' < v && x' <= y && y' >= x (and if partially invalidated, we know exactly which segment(s) are still OK.) The dereference operator of the read-only iterator then needs to check its cached v' against the underlying data structure's latest version, and if necessary skim through a small ring buffer of recent w(v, x, y) tuples to see if part of its cache must be invalidated (if v' + 1 is less than the earliest v in the ring, the reader can conservatively invalidate its entire cache.) This is a negligible amount of overhead (in the common case, a single fetch, compare, and predictable branch, and in the worst case a new transcoding that you would have had to perform anyway) per character/codepoint/byte access, and when even that is unacceptable you can simply cache a representation of the string in a buffer of known encoding and make everything else adapt to /your/ data layout. I'm intentionally not delving into the details of synchronizing reads and writes between different threads, as std::string and char[] don't provide that either, but if you really need some views to provide their own synchronization this is a (relatively) straightforward place to build it in. >1. Why can't this byte storage type not be used for all kinds of things; is not 'string' a quite bad name for it, since it is neither a string according to most programming >languages (see above) nor according to that CS definition that you are alluding to (unless you consider uninterpreted bytes to be symbols, but be quite aware that those >'symbols' would have nothing - or very little - to do with the symbols of the text represented through your construct.) Wholeheartedly agree; the view should have a name like 'text' (or 'characters', 'codepoints', 'bytes', etc.) and the underlying data structure can be string, rope, vector<char>, or boost::not_invented_yet. Sure, views don't completely solve the problem of legacy APIs that require a persistent, writable reference to a block of text (e.g.a text entry widget that maps its input to a character buffer); if you're lucky to can map the widget to the underlying_representation structure and create the views you need for other parts of the program. If you're not lucky, you might have to make a separate copy for each legacy interface and check periodically or on-demand for changes, but I'd still much rather use a data structure that forces me to make explicit copies than one that encourages me to risk sharing a single buffer between APIs that may not make the same encoding assumptions.

1 0

Survey: What should an immutable byte sequence data structure be named?
by Gregory Crosswhite 29 Jan '11

29 Jan '11

Hey everyone, To gather more data about what the community thinks an immutable byte sequence data structure should be called (given that "string" has already been taken), I have created the following poll: https://catalyst.uw.edu/webq/survey/gcross/123312 If you have an opinion on the matter, please consider visiting the above link and submitting your favorite name. Some names that have been tossed around are istring, immutable_string, chain, rope, yarn, twine, cord, but don't feel limited to these choices. Cheers, Gregory Crosswhite

7 7

Re: [boost] [string] proposal
by Ivan Le Lann 29 Jan '11

29 Jan '11

----- "Dean Michael Berris" <mikhailberis(a)gmail.com> wrote : > On Sat, Jan 29, 2011 at 8:07 PM, Ivan Le Lann <ivan.lelann(a)free.fr> > wrote: > > > > Dean Michael Berris wrote : > > > >> > >> But c_str() doesn't have to be part of the string's interface. > > > > *My* *guess* is that Artyom think that: > > > > os_func ((s1 + s2 + s3 + ... + s100).c_str()); // s for std::string > > > > is dramatically faster than: > > > > os_func ((c1 + c2 + c3 + ... + c100).to_string().c_str()); // c for > "boost::chain" > > > > And this is precisely my point as well: the one that uses boost::chain > is perfectly suited for this kind of use case in both efficiency and > clear-cut semantics. I for one don't like to make to_string() a member > either -- I much rather make it a conversion operator so boost::chain > (if we're going to call it that) can be used where interfaces take a > std::string. > [Note: I'm all for chains/ropes/etc, only looking for corner cases] I definitely agree for my example, which is a pure rope demo. linearize(chain) can give a c_str at no cost for trivial chains, and is not heavier than std::string::operator+ for non-trivial chains. Cool. Now looking at Artyom example makes me consider the quite common case where the desired output is not c_str but std::string itself. Add move optimizations on top of that: func_taking_std_string ( /*linearize*/ (my_chain_func ())); func_taking_std_string ( (my_string_func ())); No matter the way you put it, you have one unnecessary allocation, because std::string has no move constructor from chain (yet). For people eventually throwing their boost::chain into std::string, we're basically killing all move/RVO optimizations. Am I missing something? Ivan

2 1

Re: [boost] [string] Realistic API proposal
by Joe Mucchiello 29 Jan '11

29 Jan '11

Anders Dalvander wrote: > On 2011-01-28 20:12, Joe Mucchiello<jmucchiello(a)yahoo.com> wrote: >> // conversion for Windows API >> std::vector<wchar_t> vec; >> vec.resize(count_codepoints<utf8>(mystring.begin(), mystring.end())); >> convert<utf8,utf16>(mystring.begin(), mystring.end(), vec.begin()); > >I spy with my little eye a potential crash waiting to happen. >Code-points != Code-units. Dang, you're right. I used the wrong term. This is why Unicode correctness is so hard. So much for my graceful introduction to the mailing list. :-) Joe

1 0

Re: [boost] Survey: What should an immutable byte sequence data structure be named?
by Andrew Sutton 29 Jan '11

29 Jan '11

I agree with Dave. Buffer. Python uses "frozen" to describe the same (similar?) property for sets. On Jan 28, 2011 3:10 PM, "Dave Abrahams" <dave(a)boostpro.com> wrote:

5 7

Re: [boost] [string] proposal
by Ivan Le Lann 29 Jan '11

29 Jan '11

----- "Yakov Galka" <ybungalobill(a)gmail.com> wrote: > On Sat, Jan 29, 2011 at 14:07, Ivan Le Lann <ivan.lelann(a)free.fr> > wrote: > > > > > *My* *guess* is that Artyom think that: > > > > os_func ((s1 + s2 + s3 + ... + s100).c_str()); // s for > std::string > > > > is dramatically faster than: > > > > os_func ((c1 + c2 + c3 + ... + c100).to_string().c_str()); // c > for > > "boost::chain" > > > > Aren't they perform the same? Actually with lazy evaluation the latter > will > be faster. > For this example, I agree. I'm only stressing the marketing issue. Eventually, we'll need figures here. Big-sized font figures. Ivan

1 0

Re: [boost] [string] proposal
by Ivan Le Lann 29 Jan '11

29 Jan '11

Dean Michael Berris wrote : > On Sat, Jan 29, 2011 at 5:24 PM, Artyom <artyomtnk(a)yahoo.com> wrote: > > - > >> From: Dean Michael Berris <mikhailberis(a)gmail.com> > >> > >> On Sat, Jan 29, 2011 at 3:02 PM, Artyom <artyomtnk(a)yahoo.com> wrote: > >> > > >> > It would turn away 90% of users. > >> > > >> > >> It might turn you away because you obviously love std::string. > >> Generalizing is a different matter and is largely a hot-air blowing > >> exercise that is futile for convincing anybody. > >> > > > > I would say it more clear: > > > > 1. All users that use C libraries and need c_str() at boundaries > > And this is a huge amount of users that need to communicate > > with modules that are already working and ready but written in C. > > > > And this is about of half of libraries there is C is the lowest > > level API that allows easy bindings to all languages. > > > > But c_str() doesn't have to be part of the string's interface. *My* *guess* is that Artyom think that: os_func ((s1 + s2 + s3 + ... + s100).c_str()); // s for std::string is dramatically faster than: os_func ((c1 + c2 + c3 + ... + c100).to_string().c_str()); // c for "boost::chain" Regardless of the validity of my present guess, I'm quite sure that this concern (and other similar ones) will be shared many developpers. Ivan

3 2

Re: [boost] [string] Realistic API proposal
by Anders Dalvander 29 Jan '11

29 Jan '11

On 2011-01-28 20:12, Joe Mucchiello<jmucchiello(a)yahoo.com> wrote: > // conversion for Windows API > std::vector<wchar_t> vec; > vec.resize(count_codepoints<utf8>(mystring.begin(), mystring.end())); > convert<utf8,utf16>(mystring.begin(), mystring.end(), vec.begin()); I spy with my little eye a potential crash waiting to happen. Code-points != Code-units. vec has room for N code-units, but 2*N code-units may be written to it if mystring contains non-BMP characters. "Corrected" code: std::vector<wchar_t> vec; vec.resize(count_codeunits<wchar_encoding>(mystring.begin(), mystring.end())); convert<wchar_encoding>(mystring.begin(), mystring.end(), vec.begin()); I think a lot of these potential crashes could be prevented if the iterator of the new string-type (chain,text,tier,yarn) would only expose (const) code-points. Actual code-units would be hidden, and only accessed using a facade/adapter view/iterator. auto u8v = make_view<utf8_encoding>(mystring); auto u16v = make_view<utf16_encoding>(mystring); for (auto codepoint : mystring) {...} for (auto u8codeunit : u8v) {...} for (auto u16codeunit : u16v) {...} I also think there isn't a reason that the new string-type *has* to be UTF-8 internally. It could be UTF-16, UTF-32, SCSU, or CESU-8 internally for that matter. Making a view from the internal encoding to an external encoding when both encodings are the same should be a no-op. Regards, Anders Dalvander -- WWFSMD?

1 0

Re: [boost] [string] Realistic API proposal
by Anders Dalvander 29 Jan '11

29 Jan '11

On 2011-01-28 23:04, Artyom<artyomtnk(a)yahoo.com> wrote: >> > // conversion for Windows API >> > std::vector<wchar_t> vec; >> > vec.resize(count_codepoints<utf8>(mystring.begin(), mystring.end())); >> > convert<utf8,utf16>(mystring.begin(), mystring.end(), vec.begin()); >> > HRESULT hr = WriteFile(handle, vec.data(), vec.size(),&dwBytesWritten, >> > NULL); >> > ... >> > > Notice vector is not string and it requires additional copy If std::string is UTF-8 encoded (as you are suggesting, correct?), then you also requires additional copy: // conversion for Windows API std::string u8s = ...; std::wstring u16s = convert_to_utf16(u8s); HANDLE h = CreateFileW(u16s.c_str(), ...); Regards, Anders Dalvander -- WWFSMD?

2 1

[web] Broken link.
by Mostafa 29 Jan '11

29 Jan '11

FYI: on https://svn.boost.org/trac/boost/ , the following link is broken: "http://svn.boost.org/trac/boost/browser", see "You can browse the Boost Subversion repository online or retrieve Boost via ...". Mostafa

1 0