I now wonder if it'd be a good idea to move our end to end tests to a pretty slow vm instead of beefy 8 core 32gb ram machine and check which timeouts will be triggered because our app may have been unoptimized for slower environments...
For blocking presubmit checks, getting the fastest machine you can is probably reasonable. Otherwise, the advantage of the craptop approach is that it needs basically no infra work and gives an immediate impression of the site, and not CI, being slow.
If you’re willing to build some infra, there’s probably a lot more you can do—nightly slow-hardware runs come to mind immediately, browser devtools have a convincing builtin emulation of slow connections, a page displaying a graph of test runtime over time[1] isn’t hard to set up, etc.—but I don’t really have experience with that.
I kid you not a few jobs ago I found several race conditions in my code and tests by running them at the same time as a multi threaded openssl burn test. :)
Gonna bookmark that article for tomorrow, craptop duty is such a funny way to put it.
Similarly, a colleague I had before insisted on using a crappy screen. Helped a lot to make sure things stay visible on customers’ low contrast screens with horrible viewing angles, which are still surprisingly common.
Not in the x86-64 SysV ABI they aren’t. The arguments will be passed in registers (yes, even the variadic ones), so how your compiler will interpret 1[&a] is anybody’s guess. (For me, x86_64-unknown-linux-gnu-g++ -O2 yields, essentially, return a+a+a+a; which is certainly an interpretation. I’m also getting strange results from i686-unknown-linux-gnu-g++ -O2, but my x87 assembly is rusty enough that I don’t really get what’s going on there.)
Clang does the sensible thing with UB and just returns poison (a form of undefined value) in both cases, which manifests as do nothing on x86-64 and load a zero value on i386, because you need to push something on the stack and fldz is one of the cheapest ways to push something. Meanwhile, gcc is in both cases for the UB variant returning a + a + a + a;
FWIW, going back through older gcc versions, it seems i386 gcc stops implementing 'add the arguments' in version 11.1, although it's not until 15.1 that it has a sensible assembly for 'a + a + a + a'. The x86-64 gcc version is broken in 4.0 (where it stops copying the register arguments to the stack when va_start isn't called, I guess). Then it's adding xmm0 to the top 3 values on the stack until 11.1, when it's adding 'a + a + a + a', although not sensibly until version 15.1.
> return a+a+a+a; which is certainly an interpretation.
Zero is the only valid index of &a, so I presume the compiler just assumes that all the indexes in 1[&a] + 2[&a] etc must be zero. Even though they're in this case compile-time constants – the optimizer could check but why bother given that it's UB anyway. I assume modern C/C++ compilers have some flag to diagnose indexing that's known to be OOB at compile time.
I’m so used to sticking -Wall in my compilation flags the moment I write a build script that I didn’t realize it wasn’t there for this quick experiment. Yes, thank you, there are indeed diagnostics once you ask for them:
test.cpp: In function ‘double solve(double, ...)’:
test.cpp:4:20: warning: array subscript 1 is outside array bounds of ‘double [1]’ [-Warray-bounds=]
4 | return a + 1[&a] + 2[&a] + 3[&a];
| ~~~~^
test.cpp:3:58: note: at offset 8 into object ‘a’ of size 8
3 | extern "C" __attribute__((noinline)) double solve(double a, ...) {
| ~~~~~~~^
[repeat twice more for the other two accesses]
This (appears as though it) all could have happened half a decade ago had the interface-types people not abandoned[1,2] their initial problem statement of WebIDL support in WebAssembly in favour of building Yet Another IDL while declaring[3] the lack of DOM access a non-issue. (I understand the market realities that led to this, I think. This wasn’t a whim or pure NIH. Yet I still cannot help but lament the lost time.)
I worked on the original interface-types proposal a little bit before it became the component model. Two goals that were added were:
1. Support non-Web API's
2. Support limited cross language interop
WebIDL is the union of JS and Web API's, and while expressive, has many concepts that conflict with those goals. Component interfaces take more of an intersection approach that isn't as expressive, but is much more portable.
I personally have always cared about DOM access, but the Wasm CG has been really busy with higher priority things. Writing this post was sort of a way to say that at least some people haven't forgotten about this, and still plan on working on this.
> Two goals that were added were: 1. Support non-Web API's. 2. Support limited cross language interop.
I mean, surely it does not come to a surprise to anyone that either of these is a huge deal, let alone both. It seems clear that non-Web runtimes have had a huge influence on the development priorities of WebAssembly—not inherently a bad thing but in this case it came at the expense of the actual Web.
> WebIDL is the union of JS and Web API's, and while expressive, has many concepts that conflict with those goals.
Yes, another part of the problem, unrelated to the WIT story, seems to have been the abandonment of the idea that <script> could be something other than JavaScript and that the APIs should try to accomodate that, which had endured for a good while based on pure idealism. That sure would have come useful here when other languages became relevant again.
(Now with the amputation of XSLT as the final straw, it is truly difficult to feel any sort of idealism from the browser side, even if in reality some of the developers likely retain it. Thank you for caring and persisting in this instance.)
You seem to be implying that these goals were optional, but I don’t understand how #2 cross-lang interop could ever have been optional. Isn’t running non-JS languages the entire point of WebAssembly?
Given that, do you really think goal #1 non-Web APIs really added much additional delay on top of the delay necessitated by goal #2 anyway?
> but I don’t understand how #2 cross-lang interop could ever have been optional
This problem hasn't been solved outside the web either (at least not to the satisfaction of Rust fanboys who expect that they can tunnel their high level stdlib types directly to other languages - while conveniently ignoring that other languages have completely different semantics and very little overlap with the Rust stdlib).
At the core, the component model is basically an attempt to tunnel high level types to other languages, but with a strictly Rust-centric view of the world (the selection of 'primitive types' is essentially a random collection of Rust stdlib types).
The cross-language type-mapping problem is where every interop approach eventually runs aground. The component model's challenge is the same one that hit every bridge technology before it: whose type system is "canonical"?
.NET's Common Type System was supposed to be the neutral ground for dozens of languages. In practice, it had strong C# biases — try using unsigned integers from VB or F#'s discriminated unions from C#. The CLR "primitive types" were just as much a random collection as the WIT primitives are being described here.
The practical lesson from two decades of cross-runtime integration: stop trying to tunnel high-level types. The approaches that survive in production define a minimal shared surface (essentially: scalars, byte buffers, and handles) and let each side do its own marshaling. It's less elegant but it doesn't break every time one side's stdlib evolves.
WASM's linear memory model actually gets this right at the low level — the problem is everyone wants the convenience layer on top, and that's where the type-system politics start.
Except you are missing the part that CLR has a type system designed specifically for cross language interop, and is taken into account on the design of WinRT as well.
> The CLS was designed to be large enough to include the language constructs that are commonly needed by developers, yet small enough that most languages are able to support it. Any language construct that makes it impossible to quickly confirm the type safety of code was excluded from the CLS so that all languages that can work with CLS can produce verifiable code if they choose to do so.
The WIT types don’t seem random or Rust-centric to me, they’re basic types common to every major current-generation language, not just Rust but also Swift, Kotlin, even Zig. It’s true that languages with type designs from the 90s can’t take full advantage of WIT types, but WIT does seem perfectly capable of representing types from older languages, which seems like the only possible sensible design to me—older languages are supported, but that support needn’t burden interop between modern languages.
The web part is the security model and the tradeoffs between security and performance. PNaCL was in browsers but not "web" for this reason.
Like the assembly part means low-level and meant as a compilation target, not CPU instructions.
So websssembly is an assembly language for the web, like webgl is opengl for the web and webgpu are gpu APIs for the web. And behold none of those can access DOM APIs
> So webassembly is an assembly language for the web.
But is isn't, at most WAT is (the WASM text format). WASM itself is a bytecode format. Nobody calls CPU machine code 'assembly' (nitpicking, I know, but the 'web' part of the name makes a lot more sense than the 'assembly' part).
At least the 'web' part makes more sense than the 'assembly' part ;)
WASM was designed as a successor to asm.js, and asm.js was purely a web thing. While non-web-platforms were considered as a potential use case (in the sense of "using WASM outside the web should be possible", it wasn't clear at the time what the successful usages outside browsers would even look like).
It definitly had to do everything with Web, it was the agreement between Mozila going with asm.js, Chrome pushing for PNaCL, Adobe with CrossBridge, Sun with Java, Microsoft with ActiveX,....
Then some folks rediscovered UNCOL from 1958, all the systems influenced by it, and started to sell the dream of the bytecode that was going to save the world.
This is retconning the history of WASM. While WASM was designed to be also be usable outside browsers, nobody could really predict at the time what this usage would look like exactly.
I have to wonder if Apple will allow any of this to move forward in the W3C standards committee since they've been blocking many things that would make web browsers as capable as native apps.
Apple perceives web-based applications as chipping away at their app store (which makes them money), and so they cripple their Safari browser and then force all mobile browsers on iOS to use their browser engine, no exceptions, so that developers are forced to make a native app where Apple can then charge the developers (and thus the users) for a cut of any sales made through the app.
It's one reason the DOJ started suing Apple, but I fear that may have been sidelined due to politics.
This is a nice conspiracy theory but doesn't match facts like Safari implementing the WebGPU standard at a faster pace than Firefox. Safari might not be great in some areas, but their WASM/WebGPU/WebAudio support is in pretty good shape.
Push Notifications, Web Bluetooth, Web NFC, User Idle Detection, the list goes on and on. Not even counting the hundreds of #wontfix bugs in their css engine. Its not a conspiracy theory if you recognize their incentives and consistent anti-consumer behavior for fucking decades.
That is not Web, that is ChromeOS Platform, incredible how people complain about Google's taking over the Web, while pushing Electron crap and their Chrome APIs.
These are things that literally everyone but Google thinks are terrible ideas.
Why don't you flip the conspiracy around and ask yourself why Google, the world's largest advertising agency and data hoover, wants browsers, a category dominated by Google, to have unmediated access to ever more user, system, and local network data?
That's nonsense. There's plenty of people that want those APIs that don't work at Google. And it does not give Google "unmediated access" - you have to explicitly opt-in to allow the browser to use them when a website requests access to these APIs. But of course, don't let the facts get in the way of your fanboyism for Apple.
And when it's normalised for firmware updates to happen via WebHID and WebUSB? Saying no will seem as fringe as browsing the web with NoScript. It's already the main way to upgrade keyboard firmware for a lot of mechanical keyboards, and it only works on Chrome. Thrilling developments for Google.
>> But of course, don't let the facts get in the way of your fanboyism for Apple.
Mate, I didn't even mention Apple. You're the one with the fixation here. Mozilla/Firefox is also deeply opposed to these anti-features.
>Mozilla/Firefox is also deeply opposed to these anti-features.
Mozilla is irrelevant, and they don't have a hardware platform where they forbid all other browser engines from it like Apple does.
If Apple weren't total assholes and didn't forbid Chrome from actually being Chrome on iOS, then I wouldn't care, I'd simply tell users to install Chrome. But Apple forces all browsers on iOS to use Safari, which they have intentionally crippled and refuse to let other browsers use their own engine.
If you don't think that's abusive business practices and deserves the DOJ lawsuit, then you're just another Apple shill.
>> Mozilla is irrelevant, and they don't have a hardware platform where they forbid all other browser engines from it like Apple does.
>> If Apple weren't total assholes
>> Apple forces all browsers on iOS to use Safari
>> you're just another Apple shill.
I've still not even mentioned Apple once.
You seem extremely fixated on Apple.
I'm not aware of any major corporation, group, standards body, or OSS project that would agree with Google's attempts to extend the browser so deeply beyond the web. The general consensus is that it is deeply reckless.
Google failed to get stuff like WebHID into the standard - because everyone thinks it's a terrible idea - so they've just rolled it out on their own anyway, using their browser monopoly to force facts on the ground. Facts favourable to Google, unsurprisingly.
When Microsoft did this sort of thing, we used to call them out on it. I have no idea why you seem so adamant to defend this. I can only suspect that you've let yourself become completely partisan in some grand Google-Apple war that you've imagined, which is why you keep bringing up Apple out of nowhere?
I never mentioned Google. You seem really fixated on Google for some weird reason.
>The general consensus is that it is deeply reckless.
Bullshit, you made that up in your own head. Show some actual statistics instead of making shit up.
>Google failed to get stuff like WebHID into the standard - because everyone thinks it's a terrible idea
So you think you speak for "everyone"? Because you're also making that up.
>When Microsoft did this sort of thing, we used to call them out on it. I
Oh, like when they came out with XMLHTTPRequest and everyone told them to fuck off? That time? Oh, no, they actually didn't tell them to fuck off with their proprietary API, they also all implemented it in their browsers, and now it runs most of all the web.
> I have no idea why you seem so adamant to defend this.
I already spelled this out for you. Apple forbids any other browser on iOS except their own Safari. If they didn't abusively force Safari on all browsers on iOS, I would not have a problem, I would just tell users to install Chrome. But I can't, because Apple is abusive and here you are acting clueless again about what is actually going on.
You are missing the initial point here, the accusation is that apple doesn't want the web as a viable platform to develop fully fledged cross platform applications that circumvent its own moat. You just repeat the maximalist position that the web shouldn't "extend the browser so deeply beyond the web". Many people disagree with that, its the best shot we have for true cross platform applications that would force Apple to open their platform, we say the reason apple doesn't want that is for purely profit driven reasons.
Also doesn't this argument apply to WebAssembly and other standards (like WebGPU) as well? Why should I be able to render a video game in the browser but have no way to manage input devices (like multiple controllers) to make it a suitable platform for fully-fledged video games in the future? Like I understand why Apple (OR Microsoft for that matter) doesn't want Stadia-like services to suddenly run on all their devices without any cut in monetization, so naturally they sabotage such efforts in Safari...
Like here is my own reason to support that effort: I use Linux, and there are a ton of proprietary applications that if there were developed on the web platform would become accessible to me.
I understand the privacy concerns with some of those APIs, but the argument isn't that the user shouldn't have agency over those features, do you see how that's a separate conversation?
> Many people disagree with that, its the best shot we have for true cross platform applications that would force Apple to open their platform, we say the reason apple doesn't want that is for purely profit driven reasons.
And equally, Google wants their platform to replace OSes for purely profit-driven reasons of their own. I'm not saying this as some terrible indictment. They're all corporations, I don't expect anything else from them.
> Also doesn't this argument apply to WebAssembly and other standards (like WebGPU) as well?
This is a fairly consistent strain of criticism on WASM posts here on HN. The death of software as we know it; all of computing as a service, forever.
> Like here is my own reason to support that effort: I use Linux, and there are a ton of proprietary applications that if there were developed on the web platform would become accessible to me.
What makes you think future thin-client 'PC's will even be able to run anything other than a browser shell? The current requirements for Windows/iPhone/Android will just be replaced by a requirement to run an approved, TPM-clad Chromebook, cryptographically certified to be running no software other than Chrome. The ultimate in Secure Boot. But of course this will provide no actual security to end users, in a world where websites can write to your keyboard firmware. Security for corporate IP, maybe.
I genuinely think you're letting your dislike of Apple - on which I hear you, Apple's no angel - cloud your judgment here. The future Google's building is pretty dark.
But it feels like a slippery slope argument to me, like how do you go so quickly from standardized web APIs to your ChromeOS/TCPA dystopia? I think that's quite the leap to make, especially considering we already have those locked tight ecosystems right now with iOS, Android, Windows, Mac OS to varying levels of degree anyway. If proprietary applications go that route they would remain unaccessible to me, it wouldn't really change anything. But right now I can use things like figma and countless other apps because it runs on the web, it would otherwise never have been possible.
> in a world where websites can write to your keyboard firmware
again I would never relinquish control over the decision if it "can", I've been using Linux for 20+ years I already go to significant lengths to remain in control over my computing. But the fact that I can develop a cross-platform app that talks to some USB device directly via some standard web API, has benefits that outweigh the costs, that's just pragmatism.
Also if you asked me I would personally rather see Apple, Google, Microsoft and every other orphan crushing machine/publicly traded company shut down and all it's CEOs and shareholders hanging from street lamps, but personal politics aside, I'm only speaking of within the dystopia we already have anyway.
I don't think your stated interest in "remain[ing] in control over [your] computing" is at all compatible with the specific moves in tech that you're advocating for.
There's an obvious long-term trend for software to migrate from on-disk to cloud-based: from everything SaaS, through gaming, to Office suites. One common thread with all this software is that you have absolutely no control over it, which is - of course - the aim. No piracy, no unauthorised mods. Walled gardens forever in every direction.
Equally, there's a simultaneous long-term trend for 'attestation', ID checks, 'digital ID' documents, etc. Already, many bank apps refuse to run on Android devices that aren't Google-blessed and kissed. This trend is only accelerating.
In a world where paying taxes online - or accessing a bank account, or running an office suite - requires a Trusted Device™, what good is OSS? What good is software freedom? Running a Linux computer unable to interact with basic aspects of the modern world will quickly become as quaint as trying to do your day job on an Amiga.
I personally hate that I need to download app from every company for every service they offer.
On the other hand I love tje simplicity of opening webpage, do what I want to do there and forget it.
Probably 80% of app in my phone are used very rarely, often just once yet they still sit there, getting updates, requesting permissions and sometimes eating battery...
good web app can do everything native app can.
Your disagreement only remains valid because of Apple using their blocking power to quash web APIs from becoming standards. You can shill all you want for Apple, but they are being sued by the DOJ for abusive business tactics, which include leveraging their vote in the W3C to prevent web browsers on their platform from being as capable as native apps.
Sorry, but you are the one obsessed with Apple for some reason and are projecting the opposite of that (shilling) on me. I don't have any particular reason to favor Apple.
I do, however, notice that I have never used a program that was built with either a web stack or a gc language stack, that wasn't getting slower over time, wouldn't cause strange issues, and wouldn't have crippled UI to match whatever the stack's limitations have been at the time. IMO the right direction is developing (or adopting) modern native languages. If the "price" for that is some web standard being stuck, I personally am totally okay with that.
I am sick of this idea that the web browser is almost an OS. It was supposed to serve web pages.
But the app-slop is totally fine right? Apple controlling every piece of software on my phone hasn't gone too far? Empowering the web to compete with Apple and Google's native locked down options is the only viable alternative I see.
The native locked down options are the natives apps you're advocating for, I don't understand. They're the Swift/uikit or Koltin/jetpack apps. It sounds like you don't like web technology in general and would rather everyone do it the centralized Apple/Google way?
Kotlin is not native. And yes, I don't like web technology. That doesn't imply doing it in Company A / B / C way, it implies preference for compiled programs that run natively in their respective environments with full utilization of resources those environments provide, e.g. hardware access, software standards etc.
I'm building a new Wasm GC-based language and I'm trying to make as small as binaries as possible to target use cases like a module-per-UI-component, and strings are the biggest hinderance to that. Both for the code size and the slow JS interop.
I have a compiler flag to switch from wtf-8 and wtf-16 so if you compiler for your host you don't have to reencode strings. That means that strings in my language hide their byte representation, don't allow indexed access, and only have code point iterators.
Wait, this is a modern-ish ISA with a software-managed TLB, I didn’t realize that! The manual seems a bit unhappy about that part though:
> In the current version of this architecture specification, TLB refill and consistent maintenance between TLB and page tables are still [sic] all led by software.
Something like that, except you probably also want to be able to express things like “whatever the callback I’m passed can throw, I can throw all of that and also FooException”. And correctly handle the cases when the callback can throw FooException itself, and when one of the potential exceptions is dependent on a type parameter, and you see how this becomes a whole thing when done properly. But it’s doable.
The judicial system aside, it was a deliberate legislative choice (in many countries, with the US being among the most enthusiastic) to allow the executive to unilaterally designate arbitrary entities to be bad. Every system of this nature eventually gets turned against people you yourself consider good. I don’t get the surprise, frankly.
Yeah, back during Trump's first term I was hoping Congress would rein in executive power a bunch as he is prone to do stuff like this, didn't turn out that way unfortunately...
Now the main constraint on executive power seems to be due process and habeas corpus.
tl;dr the Major Questions Doctrine is something SCOTUS has been using to decide of Congress has given wide latitude. For big questions, Congress needs to be explicit. They used this in the IEEPA and tariffs case to end the arbitrary levies. Tariffs were not mentioned and are a big issue. Similar story here with claiming broad interpretation on an important issue.
I might have been misremembering, because I thought there was a three-pane browser and this one is two-pane, but I think this is what I meant: https://files.catbox.moe/0sdvpz.png (View > Object Browser or F2).
As a potential user (not the author), what jumps out at me about the two is:
OMRN: No lookaround, eager compilation, can output first match
RE#: No submatches, lazy compilation, must accumulate all matches
Both lookaround and submatch extraction are hard problems, but for practical purposes the lack of lazy compilation feels like it would be the most consequential, as it essentially disqualifies the engine from potentially adversarial REs (or I guess not with the state limit, but then it’s questionable if it actually counts as a full RE engine in such an application).
Worth mentioning (haven’t checked if the paper talks about this) that while the industry mostly forgot about derivatives and extended REs (i.e. REs with intersection and negation), academia did not. Unfortunately, there have been some pretty discouraging results: the DFA for an extended RE (including a lazy DFA implemented using derivatives, as here) is worst-case doubly exponential in the length of the expression[1], not just exponential as for normal REs. So there is a potential reason not to support intersections in one’s RE matcher, even if they are enticingly easy to implement in terms of derivatives (and even if I personally like to see experimentation in this direction).
> the DFA for an extended RE (including a lazy DFA implemented using derivatives, as here) is worst-case doubly exponential in the length of the expression
The authors seem to claim linear complexity:
> the result is RE#, the first general-purpose regex engine to support intersection and complement with linear-time guarantees, and also the overall fastest regex engine on a large set of benchmarks
The standard way to do intersection / complementation of regexes with NFAs requires determinization, which causes a huge blowup, whereas for us this is the cost of a derivative.
It is true that we cannot avoid enormous DFA sizes, a simple case would be (.*a.*)&(.*b.*)&(.*c.*)&(.*d.*)... which has 2^4 states and every intersection adds +1 to the exponent.
How we get around this in the real world is that we create at most one state per input character, so even if the full DFA size is 1 million, you need an input that is at least 1 million characters long to reach it.
The real argument to complexity is how expensive can the cost of taking a lazy derivative get? The first time you use the engine with a unique input and states, it is not linear - the worst case is creating a new state for each character. The second time the same (or similar) input is used these states are already created and it is linear. So as said in the article it is a bit foggy - Lazy DFAs are not linear but appear as such for practical cases
> The second time the same (or similar) input is used these states are already created and it is linear.
Does this imply that the DFA for a regex, as an internal cache, is mutable and persisted between inputs? Could this lead to subtle denial-of-service attacks, where inputs are chosen by an attacker to steadily increase the cached complexity - are there eviction techniques to guard against this? And how might this work in a multi-threaded environment?
Yes, most (i think all) lazy DFA engines have a mutable DFA behind a lock internally that grows during matching.
Multithreading is generally a non-issue, you just wrap the function that creates the state behind a lock/mutex, this is usually the default.
The subtle denial of service part is interesting, i haven't thought of it before. Yes this is possible. For security-critical uses i would compile the full DFA ahead of time - the memory cost may be painful but this completely removes the chance of anything going wrong.
There are valid arguments to switch from DFA to NFA with large state spaces, but RE# intentionally does not switch to a NFA and capitalizes on reducing the DFA memory costs instead (eg. minterm compression in the post, algebraic simplifications in the paper).
The problem with going from DFA to NFA for large state spaces is that this makes the match time performance fall off a cliff - something like going from 1GB/s to 1KB/s as we also show in the benchmarks in the paper.
As for eviction techniques i have not researched this, the simplest thing to do is just completely reset the instance and rebuild past a certain size, but likely there is a better way.
> Multithreading is generally a non-issue, you just wrap the function that creates the state behind a lock/mutex, this is usually the default.
But you also have to lock when reading the state, not just when writing/creating it. Wouldn’t that cause lock contention with sufficiently concurrent use?
No, we do not lock reading the state, we only lock the creation side and the transition table reference stays valid during matching even if it is outdated.
Only when a nonexistent state is encountered during matching it enters the locked region.
> are there eviction techniques to guard against this?
RE2 resets the cache when it reaches a (configurable) size limit. Which I found out the hard way when I had to debug almost-periodic latency spikes in a service I managed, where a very inefficient regex caused linear growth in the Lazy DFA, until it hit the limit, then all threads had to wait for its reset for a few hundred milliseconds, and then it all started again.
I'm not sure if dropping the whole cache is the only feasible mitigation, or some gradual pruning would also be possible.
Either way, if you cannot assume that your cache grows monotonically, synchronization becomes more complicated: the trick mentioned in the other comment about only locking the slow path may not be applicable anymore. RE2 uses RW-locking for this.
I have experienced this as well, the performance degradation of DFA to NFA is enormous and while not as bad as exponential backtracking, it's close to ReDoS territory.
The rust version of the engine (https://github.com/ieviev/resharp) just returns an Error instead of falling back to NFA, I think that should be a reasonable approach, but the library is still new so i'm still waiting to see how it turns out and whether i had any oversights on this.
Here RE2 does not fall back to the NFA, it just resets the Lazy DFA cache and starts growing it again. The latency spikes I was mentioning are due to the cost of destroying the cache (involving deallocations, pointer chasing, ...)
I'm not sure if it's with both RE2 or Rust, but some internal engines of Rust appear to allocate a fixed buffer that it constantly re-creates states into.
I'm not really familiar with the eviction technique of RE2 but I've done a lot of benchmark comparisons. A good way to really stress test RE2 is large Unicode classes, \w and \d in RE2 are ascii-only, i've noticed Unicode (\p{class}) classes very drastically change the throughput of the engine.
These claims are compatible. For instance, lex, re2c, ragel, etc. are exponential in the length of the automaton description, but the resulting lexers work in linear time[1] in the length of the string. Here the situation is even better, because the DFA is constructed lazily, at most one state per input character, so to observe its full enormity relative to the size of the needle you need an equally enormous haystack. “One state per input character” somewhat understates things, because producing each state requires a non-constant[2] amount of work, and storing the new derivative’s syntax tree a non-constant amount of space; but with hash-consing and memoization it’s not bad. Either way, derivative-based matching with a lazy DFA takes something like O(needle + f(needle) × haystack) time where I’m guessing f(n) has to be O(n log n) at least (to bring large ORs into normal form by sorting) but in practice is closer to constant. Space consumption is less of an issue because if at any point your cache of derivatives (= DFA) gets too bloated you can flush it and restart from scratch.
[1] Kind of, unless you hit ambiguities that need to be resolved with the maximal munch rule; anyways that’s irrelevant to a single-RE matcher.
[2] In particular, introductions to Brzozowski’s approach usually omit—but his original paper does mention—that you need to do some degree of syntax-tree simplification for the derivatives to stay bounded in size (thus finite in number) and the matcher to stay linear in the haystack.
[1] https://css-tricks.com/test-your-product-on-a-crappy-laptop/
reply