5 ms·

As I understand it, examples of "zero cost abstractions" would be std::string or std::map<X,Y> in C++. Reimplementing those in plain C is not a great idea, beca

As I understand it, examples of "zero cost abstractions" would be std::string or std::map<X,Y> in C++. Reimplementing those in plain C is not a great idea, because the result will be very bug-prone, and will not be (significantly) faster. The problem with these "zero cost abstractions" is that we're measuring the wrong cost. The key to efficiency is optimizing what is done, not optimizing each little line of code. std::string is a terrible idea with regards to efficiency. If it works for you chances are you should use Python instead. For anything complex, std::string is slow and has a huge memory footprint (each string has its own buffer, separately allocated from the heap). It also leads to a heavy increase in compilation times. Anecdotally, it can even be painful to depend on it when the standard library is upgraded. If you have anything beyond a few megabytes worth of text data, std::string is about the worst possible technical solution.

keldaris 7y ago
Because of everything you've outlined in your last paragraph and more, I don't know many competent C++ programmers who would call std::string or std::map "zero cost abstractions" with a straight face. That term is more commonly applied to things like CRTP, template policy classes and other abstractions that you pay for in compile time (and, depending on linker optimizations, code bloat), but not in runtime [1]. As you point out, an abstraction that does a bunch of extra work is by definition not zero cost. [1] Yes, code bloat can lead to runtime performance issues as well. Common sense coupled with linker optimizations can usually, but not always, mitigate those issues.
pdpi 7y ago
zero-cost abstractions are abstractions where the hand-written code wouldn't be any better than the abstraction. An example is how Option<Box<T>> optimises down to a single pointer in Rust — the compiler uses its knowledge of how Box<T> is non-nullable, and coopts the null value to represent the None value for the Option.
- blt 7y ago
  Is this optimization required by the language semantics or some standard (vs. being only a description of mainline rustc's implemented optimizations)?
  - steveklabnik 7y ago
    It’s a defined part of the language semantics.
    - eridius 7y ago
      Is there actually a formal language semantics definition anywhere? I thought all we had was stuff like https://doc.rust-lang.org/reference/index.html https://doc.rust-lang.org/reference/index.html which is explicitly listed as "not a formal spec".
      - steveklabnik 7y ago
        Things have different degrees of guarantees. This is something we’ve explicitly said is guaranteed.
        kurtisc 7y ago
        Where are things like this said/defined/collated?
        steveklabnik 7y ago
        We are generally at a point where if it's documented, it's guaranteed. This feature is really easy to describe, and so we have a high degree of confidence that when we say "this behavior is defined", we won't run into an edge case where we'd have to break it. So, in this case, it's a documented part of Option. I realize this answer isn't fantastic, but it's where we're at now. It's why we're working on the reference this year!
        7y ago
UnFleshedOne 7y ago
If your application's core functionality is text editing (or something similar) you might have to use something like ICU anyway, complete with its own string type and 30 megs of dlls. Or custom allocators on std::string if only memory allocation is critical. Or one of million other string classes (every freaking C++ library comes with one...) Or internal string implementation built specifically for your needs. Almost never would you drop back down to passing C-strings around though. That's just asking for buffer overflows and such.
comex 7y ago
std::string is a zero-cost abstraction joined at the hip to a non-zero-cost abstraction. At heart, it’s an abstraction over the pattern of having a uniquely-owned string pointer which is freed when the owner (object or stack frame) is freed. If you use it when you would otherwise use that pattern, the overhead should be effectively zero, at least if your STL implementation is high-quality. However, as you note, the API encourages you to use that ownership pattern everywhere, in a way you likely wouldn’t if you were doing allocation by hand – and often by accident. As the worst offender, the copy constructor allocates a new buffer and copies the whole string, though it’s implicitly called whenever you simply assign one std::string variable to another, or pass a std::string to a std::string-typed function parameter. It’s hard to avoid copies even if you know what you’re doing, and easy to misunderstand the costs if you don’t. In contrast, if you were doing allocation by hand, most of the time you’d try to just pass around pointers to existing buffers, with various ownership semantics: temporary access (borrowed), transferring ownership (move), or even using reference counting. - For the unowned case, you could always use `const std::string &`, but that only works when referencing a full existing heap allocation; it can’t represent substrings of heap allocations, or data that wasn’t on the heap in the first place. C++17 improved the situation by adding std::string_view, but you have to know to use it, especially since the API design is limited by backwards compatibility constraints: for example, std::string’s substr method still returns a std::string, not a string_view. And some people say that in ‘modern C++’ you should avoid raw unowned types to ensure safety, so if you follow their advice you would have to avoid string_view as well. - For the transferring-ownership case, C++11 added essentially zero-cost move construction that just moves the pointer from one std::string to another. But again, you have to know to use it, and the default is an expensive copy. - For reference counting, you could use std::shared_ptr, but it’s suboptimal (always using atomic reference counting even if you don’t need it, and doing a double heap indirection). Rust’s standard library has a type with similar semantics, String. But with the benefit of hindsight, it improves upon std::string in each of those areas: - For the unowned case, there’s &str, which is like C++ string_view, and it’s idiomatic to use &str everywhere instead of &String (the equivalent of C++ `const std::string &`). Slicing a String (i.e. the equivalent of substr) gives you &str; if you want to copy that into its own owned buffer, you have to do it explicitly via `.to_string()`. Also, Rust’s borrow checker verifies that your use of unowned pointers is safe, so there’s no safety/performance tradeoff. - Regarding the transferring-ownership case, Rust makes move semantics the default. Assigning one String-typed variable to another, or passing a String to a String-typed function parameter, will do a move; if you try to use the source afterwards, or if you don’t uniquely own the source, it will complain at compile time (there are workarounds depending on what you want to do). If you want to copy the data to a new heap allocation, you have to explicitly write `.clone()`. - For reference counting… well, it’s arguably less than optimal in Rust too, but better than C++. For example, the language provides atomic and non-atomic reference-counting wrapper. You can use the faster non-atomic version if you don’t need to share the value across threads (and the compiler prevents you from doing so by accident). Also, you can avoid the double indirection by using Rc<str> instead of Rc<String>. - Oh, and there is also Cow, the copy-on-write type, which represents a pointer that may or may not be owned. I don’t think the C++ STL has any equivalent; some STL implementations used to make all std::strings copy-on-write, before C++11 made that illegal, but that adds overhead for all users rather than just those who need it. Thus, I’d say Rust’s String has a better claim to being a true zero-cost abstraction.
deathanatos 7y ago
> std::string is a terrible idea with regards to efficiency. If it works for you chances are you should use Python instead Concrete examples of what you mean would help here. > For anything complex, std::string is slow and has a huge memory footprint (each string has its own buffer, separately allocated from the heap). Some implementations (e.g., GNU's) will inline small strings, and so avoid a heap allocation. Python strings always heap allocate; if you're referring to the fact that Python strings don't have to chase a pointer to the data (the string data is inlined in the Python object itself), that might have some marginal effect on speed, but for most cases it really isn't going to matter. I'm not seeing the memory comparison: `std::string` is 32 bytes on my system; Python's str reports as 49. (+ character data for each.) What would you prefer std::string did to make it more amenable to "a few megabytes of data"? (A case that, honestly, I think it handles just as well as most language's string type.) (Now, if we want to harp on std::string's Unicode support, I won't stand in your way.)
- jstimpfle 7y ago
  > Concrete examples of what you mean would help here. If it works for you, chances are that you are doing something that Python is equally suited for. And much more convenient. (Not necessarily, though). > I'm not seeing the memory comparison I didn't make one. I was saying something similar to "AVL trees vs RB trees largely doesn't matter. If you care about efficiency, you don't use either since they're both slow. If you don't care, the small speed difference doesn't matter". > What would you prefer std::string did to make it more amenable to "a few megabytes of data"? (A case that, honestly, I think it handles just as well as most language's string type.) Start by identifying strings that are immutable once they're constructed. These are usually the lion's share. Then start pooling these strings to avoid allocation overhead. This brings the overhead of a string down to a pointer or offset, and optionally a length, which costs anywhere from 4 to 16 bytes. Then, think about string interning to weed out duplicates. This reduces memory consumption significantly. Depending on average string size, up to like 80% saved. And maybe more importantly, you can pass around strings freely without any overhead - string handles fit in a single register. > (Now, if we want to harp on std::string's Unicode support, I won't stand in your way.) Unicode is a mess. For all I've ever done, byte arrays (UTF-8) were the right choice.

keldaris 7y ago

Because of everything you've outlined in your last paragraph and more, I don't know many competent C++ programmers who would call std::string or std::map "zero cost abstractions" with a straight face. That term is more commonly applied to things like CRTP, template policy classes and other abstractions that you pay for in compile time (and, depending on linker optimizations, code bloat), but not in runtime [1]. As you point out, an abstraction that does a bunch of extra work is by definition not zero cost. [1] Yes, code bloat can lead to runtime performance issues as well. Common sense coupled with linker optimizations can usually, but not always, mitigate those issues.

pdpi 7y ago

zero-cost abstractions are abstractions where the hand-written code wouldn't be any better than the abstraction. An example is how Option<Box<T>> optimises down to a single pointer in Rust — the compiler uses its knowledge of how Box<T> is non-nullable, and coopts the null value to represent the None value for the Option.

blt 7y ago
Is this optimization required by the language semantics or some standard (vs. being only a description of mainline rustc's implemented optimizations)?
- steveklabnik 7y ago
  It’s a defined part of the language semantics.
  - eridius 7y ago
    Is there actually a formal language semantics definition anywhere? I thought all we had was stuff like https://doc.rust-lang.org/reference/index.html https://doc.rust-lang.org/reference/index.html which is explicitly listed as "not a formal spec".
    - steveklabnik 7y ago
      Things have different degrees of guarantees. This is something we’ve explicitly said is guaranteed.
      - kurtisc 7y ago
        Where are things like this said/defined/collated?
        steveklabnik 7y ago
        We are generally at a point where if it's documented, it's guaranteed. This feature is really easy to describe, and so we have a high degree of confidence that when we say "this behavior is defined", we won't run into an edge case where we'd have to break it. So, in this case, it's a documented part of Option. I realize this answer isn't fantastic, but it's where we're at now. It's why we're working on the reference this year!
        7y ago

UnFleshedOne 7y ago

If your application's core functionality is text editing (or something similar) you might have to use something like ICU anyway, complete with its own string type and 30 megs of dlls. Or custom allocators on std::string if only memory allocation is critical. Or one of million other string classes (every freaking C++ library comes with one...) Or internal string implementation built specifically for your needs. Almost never would you drop back down to passing C-strings around though. That's just asking for buffer overflows and such.

comex 7y ago

std::string is a zero-cost abstraction joined at the hip to a non-zero-cost abstraction. At heart, it’s an abstraction over the pattern of having a uniquely-owned string pointer which is freed when the owner (object or stack frame) is freed. If you use it when you would otherwise use that pattern, the overhead should be effectively zero, at least if your STL implementation is high-quality. However, as you note, the API encourages you to use that ownership pattern everywhere, in a way you likely wouldn’t if you were doing allocation by hand – and often by accident. As the worst offender, the copy constructor allocates a new buffer and copies the whole string, though it’s implicitly called whenever you simply assign one std::string variable to another, or pass a std::string to a std::string-typed function parameter. It’s hard to avoid copies even if you know what you’re doing, and easy to misunderstand the costs if you don’t. In contrast, if you were doing allocation by hand, most of the time you’d try to just pass around pointers to existing buffers, with various ownership semantics: temporary access (borrowed), transferring ownership (move), or even using reference counting. - For the unowned case, you could always use `const std::string &`, but that only works when referencing a full existing heap allocation; it can’t represent substrings of heap allocations, or data that wasn’t on the heap in the first place. C++17 improved the situation by adding std::string_view, but you have to know to use it, especially since the API design is limited by backwards compatibility constraints: for example, std::string’s substr method still returns a std::string, not a string_view. And some people say that in ‘modern C++’ you should avoid raw unowned types to ensure safety, so if you follow their advice you would have to avoid string_view as well. - For the transferring-ownership case, C++11 added essentially zero-cost move construction that just moves the pointer from one std::string to another. But again, you have to know to use it, and the default is an expensive copy. - For reference counting, you could use std::shared_ptr, but it’s suboptimal (always using atomic reference counting even if you don’t need it, and doing a double heap indirection). Rust’s standard library has a type with similar semantics, String. But with the benefit of hindsight, it improves upon std::string in each of those areas: - For the unowned case, there’s &str, which is like C++ string_view, and it’s idiomatic to use &str everywhere instead of &String (the equivalent of C++ `const std::string &`). Slicing a String (i.e. the equivalent of substr) gives you &str; if you want to copy that into its own owned buffer, you have to do it explicitly via `.to_string()`. Also, Rust’s borrow checker verifies that your use of unowned pointers is safe, so there’s no safety/performance tradeoff. - Regarding the transferring-ownership case, Rust makes move semantics the default. Assigning one String-typed variable to another, or passing a String to a String-typed function parameter, will do a move; if you try to use the source afterwards, or if you don’t uniquely own the source, it will complain at compile time (there are workarounds depending on what you want to do). If you want to copy the data to a new heap allocation, you have to explicitly write `.clone()`. - For reference counting… well, it’s arguably less than optimal in Rust too, but better than C++. For example, the language provides atomic and non-atomic reference-counting wrapper. You can use the faster non-atomic version if you don’t need to share the value across threads (and the compiler prevents you from doing so by accident). Also, you can avoid the double indirection by using Rc<str> instead of Rc<String>. - Oh, and there is also Cow, the copy-on-write type, which represents a pointer that may or may not be owned. I don’t think the C++ STL has any equivalent; some STL implementations used to make all std::strings copy-on-write, before C++11 made that illegal, but that adds overhead for all users rather than just those who need it. Thus, I’d say Rust’s String has a better claim to being a true zero-cost abstraction.

deathanatos 7y ago

> std::string is a terrible idea with regards to efficiency. If it works for you chances are you should use Python instead Concrete examples of what you mean would help here. > For anything complex, std::string is slow and has a huge memory footprint (each string has its own buffer, separately allocated from the heap). Some implementations (e.g., GNU's) will inline small strings, and so avoid a heap allocation. Python strings always heap allocate; if you're referring to the fact that Python strings don't have to chase a pointer to the data (the string data is inlined in the Python object itself), that might have some marginal effect on speed, but for most cases it really isn't going to matter. I'm not seeing the memory comparison: `std::string` is 32 bytes on my system; Python's str reports as 49. (+ character data for each.) What would you prefer std::string did to make it more amenable to "a few megabytes of data"? (A case that, honestly, I think it handles just as well as most language's string type.) (Now, if we want to harp on std::string's Unicode support, I won't stand in your way.)

jstimpfle 7y ago
> Concrete examples of what you mean would help here. If it works for you, chances are that you are doing something that Python is equally suited for. And much more convenient. (Not necessarily, though). > I'm not seeing the memory comparison I didn't make one. I was saying something similar to "AVL trees vs RB trees largely doesn't matter. If you care about efficiency, you don't use either since they're both slow. If you don't care, the small speed difference doesn't matter". > What would you prefer std::string did to make it more amenable to "a few megabytes of data"? (A case that, honestly, I think it handles just as well as most language's string type.) Start by identifying strings that are immutable once they're constructed. These are usually the lion's share. Then start pooling these strings to avoid allocation overhead. This brings the overhead of a string down to a pointer or offset, and optionally a length, which costs anywhere from 4 to 16 bytes. Then, think about string interning to weed out duplicates. This reduces memory consumption significantly. Depending on average string size, up to like 80% saved. And maybe more importantly, you can pass around strings freely without any overhead - string handles fit in a single register. > (Now, if we want to harp on std::string's Unicode support, I won't stand in your way.) Unicode is a mess. For all I've ever done, byte arrays (UTF-8) were the right choice.