15 ms·
Writing your own C++ standard library from scratch
- singularity2001 2y agoI did that to get minimal wasm binaries, not sure if tree shaking today would sufficiently shrinks c++ wasm apps.
- unwind 2y agoVery nice! I like the tone and flippant energy of the post, of course, and also the way to get a nice scope by having a concrete case of a program to implement. I also appreciated the comparisons against STL, very informative. It's ... interesting that if including `vector` in STL brings in 27,000 lines, and the author's implementation of the functionality for the example program was only 1,000 lines, that the compilation time difference is only 4X. Not sure I understand that, really. But benchmarking is hard, of course. If I could come with a single suggestion it would be to include the sample program's source as text, not as a picture of text. If that means losing the pretty syntax highlighting, that's fine (by me). :)
- dwattttt 2y ago> interesting that if including `vector` in STL brings in 27,000 lines, and the author's implementation of the functionality for the example program was only 1,000 lines, that the compilation time difference is only 4X I imagine the time taken varies much more based on what's on the lines, rather than how many there are. I'm not aware of specific pathological cases, but I'm sure you could make maybe 10 lines take 20 times longer than both of those vectors put together.
- account42 2y agoIt also depends on how much of the lines end up being actually used - sure the compiler will have to parse all 27000 lines and probably do some more processing on that code but it won't have to do optimizations, register allocation and code generation on member functions or specializations you don't use.
- dbattaglia 2y agoDoesn’t c++ also make a separate type for each distinct type parameter passed to a template? If that is still true maybe it adds up when you have a lot of different vector of T types? Been a while since I read up on c++ though maybe that’s no longer true.
- fefe23 2y agoThe title is confusing. He is not reimplementing the STL. He is writing some C++ classes providing functionality that is also already implemented in STL.
- damnitbuilds 2y agoYes, and he has so far reimplemented only a tiny fraction of that STL functionality. Still interesting, despite the misleading title.
- BonusPlay 2y agoA problem I encountered while writing custom stdlib, is that certain language features expect stdlib to be there. For example, <=> operator assumes, that std::partial_ordering exists. Kinda lame. In the newer C++ standards, more and more features are unusable without stdlib (or at least std namespace).
- logicchains 2y agoAt least you have the chance to implement your own std::partial_ordering if necessary; in most languages those kind of features would be built into the compiler.
- eru 2y agoHaskell solves this nicely: your own operators just shadow the built-in operators. (And you can opt to not import the built-in operators, and only use your own. Just like you can opt not to import printf in C.)
- dataangel 2y agothat's not the issue, the problem is the operator is required by the language to return a type from the stdlib, so you have to pull in the stdlib to get that type
- eru 2y agoIn Haskell, when you define your own operators (including those that have the same name as those already defined in the standard library), you can specify your own types. There's basically no operators defined 'by the language' in Haskell, they are all defined in the standard library. (Of course, the standard library behaves as-if it defines eg (+) on integers in terms of some intrinsic introduced by the compiler.)
- account42 2y agoSometimes standard library types defined in terms of compiler-builtins like `typedef decltype(nullptr) nullptr_t` but that doesn't always make sense. E.g. for operator<=> the only alternative would be for the compiler to define std::partial_ordering internally but what is gained by that?
- daemin 2y agoI do wonder how much smaller the STL source code would be if it was pre-processed or written with only a single C++ standard in mind. So only for C++20 or only for C++23 etc. In that case how much faster would things be to compile where it doesn't need to filter through hundreds of preprocessor options?
- magicalhippo 2y agoFrom what I've read on mailing lists and whatnot, it seems a lot of complexity comes from explicit choices made, like iterators being unaffected by insertions[1] for maps and such, or time complexity guarantees that forces the implementation into certain corners. [1]: https://kera.name/articles/2011/06/iterator-invalidation-rules/ https://kera.name/articles/2011/06/iterator-invalidation-rul...
- Someone 2y ago> In that case how much faster would things be to compile where it doesn't need to filter through hundreds of preprocessor options? I think most of the time spent isn’t running the preprocessor, but parsing the declarations and definitions. Regardless, the way to speed up importing definitions in modern C++ is to use #import instead of #include. https://news.ycombinator.com/item?id=38904758 https://news.ycombinator.com/item?id=38904758 says they could import the entire std namespace in under a second (that is long when you want to run C++ as a scripting language, but not when you compile large programs)
- zerr 2y agoI recall years ago there was some kind of competition in implementing full C++ parser/front-end and standard library, or something like that, allegedly organized by nvidia.
- quuxplusone 2y agoMaybe you're thinking of cppgm.org — the "C++ Grandmaster Certification"? - http://web.archive.org/web/20190824232557/http://www.cppgm.org/ http://web.archive.org/web/20190824232557/http://www.cppgm.o... - https://news.ycombinator.com/item?id=5148895 https://news.ycombinator.com/item?id=5148895 Nothing to do with Nvidia, though.
- zerr 2y agoExactly! I believe there were rumors suggesting Nvidia involvement, but it was never confirmed. I wonder what the outcome was, did anyone become a "Certified C++ Grandmaster"?
- usrnm 2y agoYears ago every C++ project worth its salt had at least one implementation of of strings, vectors and other basic things. I hoped we finally were past that.
- pjmlp 2y agoYes, since 1998, but apparently legacy code lives on. At least in what concerns "strings, vectors and other basic things". Now if you conside something like networking part of "basic things", then it is another matter. Then again, vcpkg and conan exist now.
- w4rh4wk5 2y agoProbably not as the way things are defined in the STL is often not in line with what C++ programmers want for their code base. STL adheres to zero-cost-abstraction, which often puts safety in the backseat. Many programmers, myself included, prefer safety by default with an escape route, when its really needed. Add to that things like exceptions, locale-dependent behavior, functions with a dozen overloads, an overly complex memory allocator interface (`std::vector` vs. `std::pmr::vector`), etc. Personally, I'd prefer a common alternative to STL that focuses on these points. ETL [1] and abseil [2] come to mind, but it's not exactly what I envision. 1: https://github.com/ETLCPP/etl https://github.com/ETLCPP/etl 2: https://github.com/abseil/abseil-cpp https://github.com/abseil/abseil-cpp
- usrnm 2y agoAnd I've seen numerous explanations: someone wants more safety, someone wants less safety, someone wants locale-aware strings, someone wants ABI stability, and so on, it's an endless list. Few people are brave enough to admit that reinventing the wheel is just easier and more fun than solving problems people actually have and care about.
- w4rh4wk5 2y agoWell, I am in game development and all of the issues I listed above are actual problems that we encountered either in the past or still wrangle with today. Especially locale-dependent functions are a bitch on Windows. Edit: one more thing I'd like add is that reinventing a wheel in C++ is quite horrible as it's such a complicated language.
- leni536 2y agoThe section about the "perfect ABI stability" is rather naive. If you have a 3rd party library that exposes a class like this in a header: class SomePublicClass { pystd::HashMap<pystd::U8String, size_t> member; /*...*/ }; and distribute that 3rd party library as compiled against a particular pystd version and the headers, then that build is tied to one particular "epoch" or version of pystd, you can't safely link that library against a program that uses a different "epoch" of pystd. It's also not a new idea either. libc++ puts everything inside an inline namespace `std::__1`. There is a reason that they never bumped that.
- londons_explore 2y agojust like there is a dynamic linker that can relocate code and fixup addresses, there should be a "dynamic class-sizer" which can recognise that something is being linked against a different version of some library, but the used fields used are all still present even if the structures have changed size, and dynamically adjust all pointers into the class to match the new size.
- jeffreygoesto 2y agoComing with C++26 as far as I see... https://isocpp.org/files/papers/P2996R7.html#getting-class-layout https://isocpp.org/files/papers/P2996R7.html#getting-class-l...
- account42 2y agoReflection won't allow a linker to magically translate a class from one library version to another. It may not even be possible to do that translation at all.
- amelius 2y agoThat might be possible only if we compiled to some intermediate bytecode first, and shipped that with the code.
- leni536 2y ago
- germandiago 2y agoA bit off-topic, but as a Meson user, I would love to see C++ modules support since they start to be usable in all three big compilers. Nice experiment for the pyStd, though, as pointed out, this would break with pre-compiled 3rd party deps that use pystd in a different version :)
- dvh 2y agoI unexpectedly did some cpp few days ago and I was surprised that cpp standard library doesn't have string trim function! Everybody is rolling their own. What is the reason behind that?
- account42 2y agoWhat do you want to trim off? ASCII 0x20? Any ASCII white-space? Any Unicode white-space? Well the latter requires defined string encodings and depends on the Unicode version and you can't just use the latest without introducing subtle compatibility issues.
- deleted 2y ago[deleted]
- criddell 2y agoASCII white space (in any encoding) by default with an optional user defined set of trim characters (like Python) would probably solve the needs of 90% of people rolling their own.
- usrnm 2y agoNot all unicode whitespace characters take up exactly one byte when encoded in utf8. Not even talking about other possible encodings, just good old utf8. Let that sink in a bit, and you'll realize what a can of worms it is in a language where strings are just byte sequences.
- criddell 2y agoBecause it's tricky is exactly why it should be in the standard library. The C++ standard library should just incorporate ICU by reference IMHO.
- account42 2y agoICU is an unreasonably large dependency for something that many users won't need. Its behavior also changes with new Unicode versions which makes it incompatible with something that cares as much as backward compatibility as the C++ standard library.
- bregma 2y agoHe's not writing the C++ standard library from scratch. He's writing his own library, in a different namespace, with some similar functionality. It's easy to write a non-standard library that only satisfies your limited subset of needs. People do it all the time. It's not special. The ABI stability boast is based on having no legacy to support. It will work fine as long as everything is shipped only as code and the whole world needs to be rebuilt from scratch every time and even then, you never change any code ever even for a major bugfix. That's hardly practical in the real world where one tiny misstep on the ABI front can result in billion-dollar multinationals threatening suit (ask me how I know). It's a facile claim. The C++ standard library hasn't been known as "the STL" for almost 30 years, ever since part of the STL was modified and adopted into the C++ standard library. Most of the features he's providing implementations for were never a part of the STL (file I/O, strings, hash maps, UTF-8). I maintain an implementation of the C++ standard library for a living. It's a full-time job. It's a huge library (note to the committee: please stop) and it's really easy to mess something up. But if you want to write your own library that doesn't do what the standard library does or meet any of its requirements and implementation constraints or serve its real-world purpose, go right ahead. Just don't claim you're writing your own C++ standard library. You're not.
- jb1991 2y agoI agree, and every time I see someone refer to the standard library as the STL, I know I’m interacting with someone who doesn’t actually know the language very well.
- Longhanks 2y agoYet, Microsoft's own implementation was open sourced in 2019 in the repo "microsoft/STL" and in the second line of the readme claims the C++ standard library be also known as STL and the readme continues to use the term STL to refer to the C++ standard library. (https://github.com/microsoft/STL https://github.com/microsoft/STL, https://github.com/microsoft/STL/commit/219514876ea86491de191ceaa88632616bbc0f19 https://github.com/microsoft/STL/commit/219514876ea86491de19..., https://github.com/microsoft/STL/blame/main/README.md#L3 https://github.com/microsoft/STL/blame/main/README.md#L3)
- larusso 2y agoHow will this year release scale when you need to work with newer compilers? I don‘t write cpp so I honestly don‘t know. Do you need to freeze your version of the compiler forever? Or is gcc / clang backwards compatible? Or do you sprinkle tons of pragmas on the files to control this? What I mean is how can you make sure your version one API is still compiling in the future. Take the counter example of ruby for instance. I could write a package with lots of namespaces and declare v1 frozen. But I still need to potentially update the code so it can run in newer versions of the runtime. Edit: typos
- 0xffff2 2y agoOverwhelmingly, new compilers will compile old code just fine. IIRC, the only time old code is broken intentionally is when fixing a bug in the compiler itself causes the code to break.
- quibono 2y agoA bit off-topic maybe, what is a good open source library to read through to see some clean&modern C++? I've not dealt with the language in a bit and was thinking of diving back in
- jeroenhd 2y agoI've always found SerenityOS to have quite nice C++ source code. The project runs on very recent versions of C++ (to the point where the standard compilation script for Ubuntu will compile a modern compiler first) and the OS intentionally doesn't stick to POSIX, allowing some very nice API improvements that only work in a C++-first world. Its main author moved on to Ladybird, though, so I haven't really browsed the code recently. I'm not sure if SerenityOS uses concepts and other such recent additions.
- pjmlp 2y agoIn any case, having a go at Tour of C++ book is a good way to read about modern idioms.
- xdavidliu 2y agothe most recent version has `import std;` in the very first hello world, which to my knowledge is not close to working in the vast majority of compilers.
- pjmlp 2y agoIt works alright on VC++ and clang/CMake/ninja. The main issue is VS where the EDG frontend still hasn't been properly updated, and clang/cmake can't handle header units. GCC is lagging behind, and everyone else is anyway mostly catching up to C++17. For my hobby coding, I am mostly doing C++23 on VC++, so it is modules all the way. At work, it is still C++17 land on native libraries for managed languages.
- atombender 2y ago> The C++ standard library (also know as the STL) The C++ Standard Library is not the same as the STL. The STL is the Standard Template Library, which provides containers such as vectors, as well as related functionality like iterators. The C++ Standard Library includes STL, but is a lot more, including things like I/O, math, concurrency, and so on.
- Longhanks 2y agoThe maintainers of Microsoft's C++ standard library use the term interchangeably, both "STL" and "C++ standard library" refer to the same thing. https://github.com/microsoft/STL/blame/main/README.md#L3 https://github.com/microsoft/STL/blame/main/README.md#L3
- atombender 2y agoProbably a historical artifact. It has never been the correct term.
- grandempire 2y agoThere is a science to designing reusable containers and algorithms, and it’s based on research like Art of Computer programming and you can learn more by reading primary sources about the design of STL. STL can absolutely be improved, but posts like this indicate most programmers are clueless about how it works, and not in a position to learn from its mistakes and make something better. If we are serious about code reuse we need to study these ideas and learn how to actually write libraries. The alternative is the npm/crates model - where you throw together 100 different open source concoctions and hope it works.
- SleepyMyroslav 2y agoRant. I do not see any improvement in the outcome code. Lets not nitpick on fast parsing and just scroll through unnecessary code actions. > ... u8line(move(line)) We are not reusing parsed line object between iterations. Forcing fresh allocation per line. > auto words = ... Fresh allocation per line. > lookup/insert Lookup and hashing done 2 times for each word. Each unique word individually allocated on the heap. > stats.push_back Not preallocated. Likely doing full allocate + copy per each word. > sort_relocatable Could have been faster with additional memory provided. But this is minor because sorting probably was not ideal in the first place. and the icing on the cake: >printf("%d ... (int)count ... As old saying goes "One can write Fortran program in any language". There are zero reasons to write non type safe text output in 2025 in C++ but here we are. TLDR. One can name their foundation library any name and use any namespace it does not change how the code written much. Right?
- cozzyd 2y agoIs there an explanation for the py prefix? Is that some sort of cruel joke?