> I think they made some choices that eventually led to the parser being too complex, largely due to the problem of representing what was parsed.
No, the complexity of the parser can be attributed to the incremental parsing. ble.sh implements an incremental parser where one can update only the necessary parts of the previous syntax tree when a part of the command line is modified. I'd probably use the same data structure (but better abstracted using classes) even if I could implement the parser in C or in higher-level languages.
That's the way to go. I don't even consider other shallow and ad-hoc approaches as actually parsing it.
I've been working on a state-machine based parser of my own. It's hard, I'm targetting very barebones interpreters such as posh and dash. Here's what it looks like
(not fully working example, but it gives an idea of what pure POSIX shell parsing looks like, ignore the aliases, they'll not be in the final version).
> I'm glad to hear you can see the effect of the optimizations ! That took a long time :-)
Yep, been testing osh since 0.9! Still a long way to go to catch up with ksh93 though, it's the fastest of all shells (even dash) by a wide margin.
By beating bash, you also have beaten zsh (it's one of the slowest shells around).
Yes thanks for testing it. I hope we can get to "awk/Python speed" eventually, but I'm happy to have exceeded "bash and zsh speed"!
And I did notice that zsh can be incredibly slow -- just the parser itself is many times slower than other shells
A few years ago a zsh dev came on Zulip and wished us luck, probably because they know the zsh codebase has a bunch of technical debt
i.e. these codebases are so old that the maintainers only have so much knowledge/time to improve things ... Every once in awhile I think you have to start from scratch :)
You may well already be aware, but just in case you aren't, your bin-true benchmark mostly measures dynamic loader overhead, not fork-exec (e.g., I got 5.2X faster using a musl-gcc statically linked true vs. glibc dynamic coreutils). { Kind of a distro/cultural thing what you want to measure (static linking is common on Alpine Linux, BSDs, less so on most Linux), but good to know about the effect. }
Yup, I added an osh-static column there, because I know dynamic linking slows things down. (With the latest release, we have a documented build script to make osh-static, which I tested with GNU libc and musl: https://oils.pub/release/latest/doc/help-mirror.html)
Although I think the CALLING process (the shell) being dynamically linked affects the speed too, not just the CALLED process (/bin/true)
I'd like to read an analysis of why that is! And some deeper measurements
The calling process being dynamically linked might impact fork() a lot to copy the various page table setups and then a tiny bit more in exec*() to tear them down. Not sure something like a shell has vfork() available as an option, but I saw major speed-ups for Python launching using vfork vs. fork. Of course, a typical Python instance has many more .so's linked in than osh probably has.
One could probably set up a simple linear regression to get a good estimate of added cost-per-loaded .so on various OS-CPU combos, but I am unaware of a write up of such. It'd be a good assignment for an OS class, though.
Parsing is a trivial, rejecting invalid input is trivial, the problem is representing the parsed content in a meaningful way.
> bash completion scripts try to parse bash in bash
You're talking about ble.sh, right? I investigated it as well.
I think they made some choices that eventually led to the parser being too complex, largely due to the problem of representing what was parsed.
> Also, OSH is now FASTER than bash, in both computation and I/O.
According to my tests, this is true. Congratulations!