Giving C++ std:regex a C makeover
nullprogram.com
nullprogram.com
This is a pretty cool hack. Makes me want to write a regex library again.
(minus the known foot-guns like strcpy() that we learned long ago were not great)
The only reason they happen to be available on Windows is that Microsoft, in an uncharacteristicly freak stroke of respect for existing standards, decided to make WinSock (mostly) function-for-function compatible with BSD sockets.
Both are available if you use --std=c89 on gcc and clang. At this point it is safe to assume they are available unless you're doing something weird like writing C for some tiny microcontroller. Practically speaking this has been true for at least 20 years.
This is irrelevant - that switch doesn’t have anything to do with controlling functionality not provided by the C standard library. Since poll and select aren’t part of it to begin with it doesn’t affect their availability.
epoll and signalfd will be available (on a gcc target where they are available obviously) as well with that switch I don’t think that makes them C standard library functionality.
select/poll differs enough across common platforms. In MSVC, poll isn’t there, sure you can emulate but now the goal post moving is getting ridiculous. The arguments to select are only superficially compatible (A practical example is that POSIX select supports pipes, but this will not work on Windows outside of specific environments or 3rd party implementations)
https://learn.microsoft.com/en-us/windows/win32/api/winsock2...
The whole moving around of definition of what is the C standard library just because of popularity seems unproductive. ("You can do nonblocking IO using the C std library." -- no, you can't) Most popular 3rd party libraries support or can easily support the most popular targets due in large part to them being popular, that means "in practice, they exist everywhere it makes sense." Does this mean all popular 3rd party libraries are part of the C standard library?
Colloquially redefining terms like what is the C standard library just sows confusion with no benefit (as was illustrated earlier in regards to threads; C11 threads are not pthreads), just say what you mean in this case.
TBF though, I guess one can implement non-blocking IO in C11 with just the stdlib by moving blocking IO calls into threads.
If you're writing C code in 2024 and your target is a system that has an OS, then it's safe to use select and poll. They're going to be there. This hand wringing over "oh no, they aren't supported on every platform" is silly because the only platforms where they don't exist are the ones where they don't make sense anyway.
C11 added threading to the stdlib (https://en.cppreference.com/w/c/thread).
MSVC is really late to the party (as always): https://devblogs.microsoft.com/cppblog/c11-threads-in-visual...
AFAIK select() and poll() are still not supported in MSVC though. IIRC at least select() is provided by 'WinSock' (the Berkeley socket API emulation on Windows), but it only works for socket handles, not for C stdlib file descriptors.
In general, if you're used to POSIX, Windows and MSVC is a world of pain. Sometimes a function under the same name exists but works differently, and sometimes a function exists with an underscore, and still works differently. It's usually better to write your own higher level wrapper functions which call into POSIX functions on UNIX-like operating systems, and into Win32 functions on Windows (e.g. ignoring the C stdlib for those feature areas).
Mostly because before Satya took over, C on Windows was considered a done deal, and everything was to be done in C++, with C related updated only to the extent required by ISO C++ compliance.
https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
Eventually the change of direction in Microsoft's management, made them backtrack on that decision.
Additionally, in what concerns C++ compliance, they are leading up to C++23 in compliance, while everyone else is still missing on full modules, some concepts stuff, parallel STL,...
Although something has happened, as the VC++ team has switched away to something else, maybe due to the Rust adoption, .NET finally being AOT proper with lowlevel stuff in C#, or something else.
https://old.reddit.com/r/cpp/comments/1ea6gho/microsoft_when...
Not on Windows. My target systems include Windows. The world is much larger than just Linux/POSIX.
Also some software still target windows xp and this one doesn't even have poll, only select
What is grep going to do while it waits for data?
Two things:
- Search the data it’s already read in. If data is coming in fast enough, it’s better to read and search in parallel rather than alternating.
- If this is a recursive grep, then list, open, or read from additional files.
Even so, thread pools work fine for this kind of thing. An optimized grep already wants to use threads to split the CPU work into parallelizable chunks (where helpful), so using threads for syscalls too shouldn’t make much difference.
However, for recursive grep, you might need to open large numbers of small files, in which case syscall latency might be a big enough factor that something like io_uring would be significantly faster.
Disclaimer: I’m mostly thinking about tools like ripgrep that are only grep-like. I’m not aware of any actual grep implementations that use parallelism to the same extent. But there’s no reason a grep implementation couldn’t do that; it’s just that most grep implementations were written in the age of single-core processors. Also note that I don’t actually know much about ripgrep’s implementation, so this post is mostly speculative.
The kernel handles that. Your program works on the data that’s available while the pipe is filling up again.
> If this is a recursive grep
As you said. This is modeled best by multiple threads or processes, each navigating through their structure.
...with a design philosophy of composition. Rather than a hundred tools that each try to make too-clever predictions about how to parallelize your work, the idea is to have small streamlined tools that you can compose into the optimal solution for your task. If you need parallelization, you can introduce that in the ways you need to using other small, streamlined tools that provide that.
It had nothing to do with some prevalence of "single-core processors" and was simply just a different way of building things.
I don't relish the idea of splitting sections of a file up into N chunks and running N grep's in parallel, and would much rather that kind of "smarts" to be in the grep tool
If you need to do n parallel searches what better arrangement do you propose?
This. A big reason behind Rust managing to get some traction from the onset was how Rust presented itself as an alternative to C for system's programming that offered a modern set of libraries designed with the benefit of having decades of usability research.
What did convince me was being able to prototype things for the C project I was working on while having access to a standard library that included basic data structures, synchronisation primitives, and I/O handling in a way that used best practices from recent decades. Everything else was just a bonus that I got to learn and use as I went.
Unfortunely they came up when UNIX and C were the cool kids on the block, and who cares about a buffer overflow or a few miscompilations due to UB, any good coder is going to get them right anyway, no need for straighjaket programming languages.
Whether you want to use that is another question.
As proven by early editions of Petzold famous book.
This comprehensive article goes over the problems of memory allocation, how programmers and educators have been trained to wrongly think about the problem, and how the concept of arenas solve it.
As someone who spends most of his time in garbage collected languages, this was wildly fascinating to me.
As it stands, std::regex should come with a warning label. It’s fine for occasional use. As part of a parser, it’s not. Slow is better than broken, until slow is broken.
The purpose of the C++ standard library is to provide well-tested, well-documented general functionality. If you have specific requirements and have an implementation or API that meets your requirements better than what the C++ standard library supplies, that's great. You're encouraged to use that instead.
If you have an implementation of std::regex that meets all the documented requirements and is provably faster under all or most circumstances than my implementation is, then submit it upstream. It's Free software and it wouldn't be the first time improved implementations of library code have been suggested and accepted by that project. Funny how no one has done that for std::regex in over a decade though, despite the complaints.
See https://stackoverflow.com/questions/70583395/why-is-stdregex...
Problematic macro in the header, custom string type compatible with nothing else in C, and I have no idea where the arena type comes from.
Having it magically deallocate memory is nice, but will confuse C programmers reading the caller.
Honestly, adding -lre to the linker is just much easier, and that library comes with docs too.
They are fully aware of -lre and assume that everyone else is too. This isn't about just achieving regex somehow. It's about avoiding the crt and gc and c++ in general while using an environment that normally includes all that by default.
You don't redefine new just to get regex. Obviously there must be some larger point and this regex is just some zoomed-in detail example of existing and operating within that larger point.
I guess the entire post could be seen as an exercise in wrapping C++ to C with nice memory-handling properties and so on, but it would also be fine to be open and upfront about that, in my opinion.
my_audio_sdk_init(&arena, sizeof(arena)); // char arena[65536]; // or something like this
I do something quite different. I design the API so any data returned by the library function is allocated by the caller. This means the caller has full control over what style of memory management works best.
For example, you can then choose to use stack allocation, RAII, malloc/free, the GC, static allocation, etc.
For a primitive example, snprintf.
Even boost.regex on which std::regex is originally based, performs better because they can afford to break ABI.