jumprope-rs
WebKit
Our great sponsors
jumprope-rs | WebKit | |
---|---|---|
8 | 151 | |
129 | 7,438 | |
- | 2.8% | |
4.0 | 10.0 | |
11 months ago | 3 days ago | |
Rust | ||
GNU General Public License v3.0 or later | - |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
jumprope-rs
-
Text Showdown: Gap Buffers vs. Ropes
Thanks for all the work in bootstrapping this part of the ecosystem! I opened an issue[1] on the memory issue for jumprope. It seems to really come down to the large size of skiplist nodes relative to the text.
I did some testing with JumpRopeBuf, but ultimately did not include it because I was comparing things from an "interactive editor" perspective where edits are applied immediately instead of a collaborative/CRDT use case where edits are async. But it did perform very well as you said! I feel like JumpRopeBuf feels similar to a piece table, where edits are stored separately and then joined reading.
[1] https://github.com/josephg/jumprope-rs/issues/5
-
How to Survive Your Project's First 100k Lines
Every piece of a large program should be tested like this. And if you can, test your whole program like this too. (Doable for most libraries, databases, compilers, etc. This is much harder for graphics engines or UI code.)
I've been doing this for years and I can't remember a single time I set something like this up and didn't find bugs. I'm constantly humbled by how effective fuzzy bois are.
This sounds complex, but code like this will usually be much smaller and easier to maintain than a thorough unit testing suite.
Here's an example from a rope (complex string) library I maintain. The library lets you insert or delete characters in a string at arbitrary locations. The randomizer loop is here[1]. I make Rope and a String, then in a loop make random changes and then call check() to make sure the contents match. And I check and all the expected internal invariants in the rope data structure hold:
[1] https://github.com/josephg/jumprope-rs/blob/ae2a3f3c2bc7fc1f...
When I first ran this test, it found a handful of bugs in my code. I also ran this same code on a few rust rope libraries in cargo, and about half of them fail this test.
-
Announcing crop, the fastest UTF-8 text rope for Rust
Jumprope author here. Thanks for the quick test! I just updated the benchmarks in jumprope/rope_benches to include Crop, and it looks to me like jumprope is about 2x faster than crop:
-
Google's OSS-Fuzz expands fuzz-reward program to $30000
I’d go further and say that writing most software without fuzz testing is insane. Fuzz testing is one of those things they should teach in school. They’re a super useful technique - up there with TDD and it’s a tragedy they aren’t more wildly used.
Fuzzers are so good because they find so many bugs relative to programmer effort (lines of code). They’re some of the most efficient testing you can do. If I had to choose between a full test suite and a fuzzer, I’d choose the fuzzer.
I use fuzzers whenever I have a self contained “machine” in my code which should have well defined behaviour. For example, a b-tree. I write little custom fuzzers each time. The fuzzing code randomly mutates the data structure and keeps a list of the expected btree content. Then periodically I verify that the list and the btree agree on what should be contained inside the list. In the project I’m working on at the moment, I have about 6 different fuzzers sprinkled throughout my testing code. (Btree fuzzer, rope fuzzer, file serialisation fuzzer, a few crdt fuzzers, and so on).
Writing fuzzers is quite devastating for the ego. Usually the first time I point a fuzzer at my code, even when my code has a lot of tests, the fuzzer throws an assertion failure instantly. “Iteration 2 … the state doesn’t match what was expected”.
Getting a fuzzer running all night without finding any bugs is a balm for the soul.
The code looks like this, if anyone is curious. Here’s a fuzzer for a rope (fancy string) implementation: https://github.com/josephg/jumprope-rs/blob/master/tests/tes...
-
The case against an alternative to C
Yep. A few years ago I implemented a skip list based rope library in C[1], and after learning rust I eventually ported it over[2].
The rust implementation was much less code than the C version. It generated a bigger assembly but it ran 20% faster or so. (I don't know why it ran faster than the C version - this was before the noalias analysis was turned on in the compiler).
Its now about 3x faster than C, thanks to some use of clever layered data structures. I could implement those optimizations in C, but I find rust easier to work with.
C has advantages, but performance is a bad reason to choose C over rust. In my experience, the runtime bounds checks it adds are remarkably cheap from a performance perspective. And its more than offset by the extra optimizations the rust compiler can do thanks to the extra knowledge the compiler has about your program. If my experience is anything to go by, naively porting C programs to rust would result in faster code a lot of the time.
And I find it easier to optimize rust code compared to C code, thanks to generics and the (excellent) crates ecosystem. If I was optimizing for runtime speed, I'd pick rust over C every time.
[1] https://github.com/josephg/librope
[2] https://github.com/josephg/jumprope-rs
-
Linked lists and Rust
Linked lists are also the basis for skip lists - which are awesome. One of the only data structures I know of which needs a random number generator to work correctly. I have a rope implementation that I tidied up over the last few days which uses a skip list. Its several times faster than the next fastest library I know of (ropey). They're both O(log n), but for some reason jumprope (with skip lists) still ended up several times faster than ropey's b-trees.
WebKit
-
GPU Compute in the Browser at the Speed of Native: WebGPU Marching Cubes
Multiple engineers are working on adding it back: https://github.com/WebKit/WebKit/pulls?q=is%3Apr+is%3Aclosed...
-
HTML Streaming and DOM Diffing Algorithm
Since 2023 Chrome announced the View Transition API, and it looks like Safari is also going to support it soon.
-
Towards memory safety with ownership checks for C
One heap per type.
Here’s an allocator optimized for that use case.
https://github.com/WebKit/WebKit/blob/main/Source/bmalloc/li...
-
Bun, JavaScript, and TCO
To use this in Bun, you’d have to start Bun with the environment variable “BUN_JSC_useDollarVM=1” and then $vm.createBuiltin(mySourceCodeString)
When using this intrinsic, if any of the arguments are incorrect or it cannot otherwise enable it, the entire process will probably crash. In debug builds of JSC it will have a nicer assertion failure but that is not enabled in release builds
Example code: https://github.com/WebKit/WebKit/blob/17351231b4dedb62d81721...
also happy to answer any questions about Bun
-
Show HN: Rem: Remember Everything (open source)
Ah, good, let me introduce you to the wonderful world of the Chrome Devtools Protocol! (fka Chrome Remote Debugging Protocol)
I love this API for almost everything browser related. I built my RBI product atop this (BrowserBox: https://dosyago.com), and I think it's a drastically underrated API.
Also, it works out of the box in Edge, Brave, Chromium, and many parts of CRDP are supported by Firefox and Safari^1
1: See for example: https://github.com/WebKit/webkit/tree/main/Source/JavaScript...
- WebGPU now available for testing in Safari Technology Preview
-
Disabling iOS Personalized Ads tells kernel to kill daemon every 3 seconds
No, it's unrelated.
https://github.com/WebKit/WebKit/commit/064df1a9f395f8c6e32c...
- Apple's Safari browser is still vulnerable to Spectre attacks
-
Replacing WebRTC: real-time latency with WebTransport and WebCodecs
It's being worked on now: https://github.com/WebKit/WebKit/pull/17320
-
iLeakage: Browser-Based Timerless Speculative Execution Attacks on Apple Devices
It is different. The cross-site navigation flag is a couple of years old. It was enabled by default for iOS in November 2018 for example https://github.com/WebKit/WebKit/commit/e191fc8c412850cb9fd0...
What are some alternatives?
crop - 🌾 A pretty fast text rope
chromium - The official GitHub mirror of the Chromium source
librope - UTF-8 rope library for C
otter-browser - Otter Browser aims to recreate the best aspects of the classic Opera (12.x) UI using Qt5
Odin - Odin Programming Language
cname-trackers - This repository contains a list of popular CNAME trackers
EmeraldC - The Ultimate C Preprocessor
fingerprintjs - Browser fingerprinting library. Accuracy of this version is 40-60%, accuracy of the commercial Fingerprint Identification is 99.5%. V4 of this library is BSL licensed.
buffet - All-inclusive Buffer for C
gecko-dev - Read-only Git mirror of the Mercurial gecko repositories at https://hg.mozilla.org. How to contribute: https://firefox-source-docs.mozilla.org/contributing/contribution_quickref.html
fast-check - Property based testing framework for JavaScript (like QuickCheck) written in TypeScript
uBlock-Safari - uBlock Origin - An efficient blocker for Chromium, Firefox, and Safari. Fast and lean.