Mike Gerwitz

Activist for User Freedom

Commit message (Collapse)AuthorAgeFilesLines
* tamer: Update dependenciesMike Gerwitz2022-03-111-16/+16
| | | | | | | Petgraph was previously held back due to petgraph-graphml. I'd like to transition away from that at some point, given that it's tied to petgraph and also pulls in xmlns, on top of quick-xml and our XIR, but that can come down the line.
* tamer: Remove tests invoking cargo and associated libsMike Gerwitz2021-12-021-203/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | There are a number of reasons for this, where the benefits do not make up for the losses. First: this is actually invoking cargo. Not only is this not necessary, but it's not desirable: cargo by default hits the network and does all sorts of other stuff, when all we want to do is invoke the executable. So the tests aren't really testing the right thing in that sense. See the previous commit for more information. The way it invokes cargo is different than the way the Makefile invokes cargo, so on my system, it's actually invoking a _different cargo_! This is causing problems, in particular with lock files, which causes my tests to fail. Importantly, this also removes a _lot_ of dependencies, which removes a lot of supplier chain risk and a lot of code to audit. This provides significant security benefits, especially given that what was being tested was rather small, and could be done in a shell script. TAMER will receive significant system testing later on. But for now, none of this was worth it. Further audits of dependencies will come later on. I've always been fairly insistent on keeping the dependency graph small and auditable, but recent supply chain attacks have given me a better way to rationalize the security risk. Further, I'm the only one on this project right now.
* tamer: xir::XirString: WIP implementation (likely going away)Mike Gerwitz2021-11-101-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I'm not fond of this implementation, which is why it's not fully completed. I wanted to commit this for future reference, and take the opportunity to explain why I don't like it. First: this task started as an idea to implement a third variant to AttrValue and friends that indicates that a value is fixed, in the sense of a fixed-point function: escaped or unescaped, its value is the same. This would allow us to skip wasteful escape/unescape operations. In doing so, it became obvious that there's no need to leak this information through the API, and indeed, no part of the system should care. When we read XML, it should be unescaped, and when we write, it should be escaped. The reason that this didn't quite happen to begin with was an optimization: I'll be creating an echo writer in place of the current filesystem-based copy in tamec shortly, and this would allow streaming XIR directly from the reader to the writer without any unescaping or re-escaping. When we unescape, we know the value that it came from, so we could simply store both symbols---they're 32-bit, so it results in a nicely compressed 64-bit value, so it's essentially cost-free, as long as we accept the expense of internment. This is `XirString`. Then, when we want to escape or unescape, we first check to see whether a symbol already exists and, if so, use it. While this works well for echoing streams, it won't work all that well in practice: the unescaped SymbolId will be taken and the XirString discarded, since nothing after XIR should be coupled with it. Then, when we later construct a XIR stream for writting, XirString will no longer be available and our previously known escape is lost, so the writer will have to re-escape. Further, if we look at XirString's generic for the XirStringEscaper---it uses phantom, which hints that maybe it's not in the best place. Indeed, I've already acknowledged that only a reader unescapes and only a writer escapes, and that the rest of the system works with normal (unescaped) values, so only readers and writers should be part of this process. I also already acknowledged that XirString would be lost and only the unescaped SymbolId would be used. So what's the point of XirString, then, if it won't be a useful optimization beyond the temporary echo writer? Instead, we can take the XirStringWriter and implement two caches on that: mapping SymbolId from escaped->unescaped and vice-versa. These can be simple vectors, since SymbolId is a 32-bit value we will not have much wasted space for symbols that never get read or written. We could even optimize for preinterned symbols using markers, though I'll probably not do so, and I'll explain why later. If we do _that_, we get even _better_ optimizations through caching that _will_ apply in the general case (so, not just for echo), and we're able to ditch XirString entirely and simply use a SymbolId. This makes for a much more friendly API that isn't leaking implementation details, though it _does_ put an onus on the caller to pass the encoder to both the reader and the writer, _if_ it wants to take advantage of a cache. But that burden is not significant (and is, again, optional if we don't want it). So, that'll be the next step.
* tamer: Start of XIR-based xmle writerMike Gerwitz2021-09-281-0/+7
| | | | | | | | | | | | | | | | | | | | | This has been a long time coming, and has been repeatedly stashed as other parts of the system have evolved to support it. The introduction of the XIR tree was to write tests for this (which are sloppy atm). This currently writes out the `xmle` header and _most_ of the `l:dep` section; it's missing the object-type-specific attributes. There is, relatively speaking, not much more work to do here. The feature flag `wip-xir-xmle-writer` was introduced to toggle this system in place of `XmleWriter`. Initial benchmarks show that it will be competitive with the quick-xml-based writer, but remember that is not the goal: the purpose of this is to test XIR in a production system before we continue to implement it for a frontend, and to refactor so that we do not have multiple implementations writing XML files (once we echo the source XML files). I'm excited to get this done with so that I can move on. This has been rather exhausting.
* tamer: ir::asg::ident: AsRef impls for SymbolId typesMike Gerwitz2021-09-201-0/+7
| | | | | | | | | | | | | | This commit will make more sense once the broader context is committed, but it's needed for lowering from `Sections` into a XIR stream. This will also change once we pre-allocate symbols, like rustc, when the interner is initialized. This is my first use of the `paste` crate, which is used to generate identifiers. So this is partly an experiment, and it seems much better than having to write a proc macro, at least at this point in time. If this code stays around, it'll probably be generalized further and used elsewhere, but I'd prefer not to go this route long-term.
* tamer: memchr benchesMike Gerwitz2021-08-181-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This adds benchmarking for the memchr crate. It is used primarily by quick-xml at the moment, but the question is whether to rely on it for certain operations for XIR. The benchmarking on an Intel Xeon system shows that memchr and Rust's contains() perform very similarly on small inputs, matching against a single character, and so Rust's built-in should be preferred in that case so that we're using APIs that are familiar to most people. When larger inputs are compared against, there's a greater benefit (a little under ~2x). When comparing against two characters, they are again very close. But look at when we compare two characters against _multiple_ inputs: running 24 tests test large_str::one::memchr_early_match ... bench: 4,938 ns/iter (+/- 124) test large_str::one::memchr_late_match ... bench: 81,807 ns/iter (+/- 1,153) test large_str::one::memchr_non_match ... bench: 82,074 ns/iter (+/- 1,062) test large_str::one::rust_contains_one_byte_early_match ... bench: 9,425 ns/iter (+/- 167) test large_str::one::rust_contains_one_byte_late_match ... bench: 123,685 ns/iter (+/- 3,728) test large_str::one::rust_contains_one_byte_non_match ... bench: 123,117 ns/iter (+/- 2,200) test large_str::one::rust_contains_one_char_early_match ... bench: 9,561 ns/iter (+/- 507) test large_str::one::rust_contains_one_char_late_match ... bench: 123,929 ns/iter (+/- 2,377) test large_str::one::rust_contains_one_char_non_match ... bench: 122,989 ns/iter (+/- 2,788) test large_str::two::memchr2_early_match ... bench: 5,704 ns/iter (+/- 91) test large_str::two::memchr2_late_match ... bench: 89,194 ns/iter (+/- 8,546) test large_str::two::memchr2_non_match ... bench: 85,649 ns/iter (+/- 3,879) test large_str::two::rust_contains_two_char_early_match ... bench: 66,785 ns/iter (+/- 3,385) test large_str::two::rust_contains_two_char_late_match ... bench: 2,148,064 ns/iter (+/- 21,812) test large_str::two::rust_contains_two_char_non_match ... bench: 2,322,082 ns/iter (+/- 22,947) test small_str::one::memchr_mid_match ... bench: 4,737 ns/iter (+/- 842) test small_str::one::memchr_non_match ... bench: 5,160 ns/iter (+/- 62) test small_str::one::rust_contains_one_byte_non_match ... bench: 3,930 ns/iter (+/- 35) test small_str::one::rust_contains_one_char_mid_match ... bench: 3,677 ns/iter (+/- 618) test small_str::one::rust_contains_one_char_non_match ... bench: 5,415 ns/iter (+/- 221) test small_str::two::memchr2_mid_match ... bench: 5,488 ns/iter (+/- 888) test small_str::two::memchr2_non_match ... bench: 6,788 ns/iter (+/- 134) test small_str::two::rust_contains_two_char_mid_match ... bench: 6,203 ns/iter (+/- 170) test small_str::two::rust_contains_two_char_non_match ... bench: 7,853 ns/iter (+/- 713) Yikes. With that said, we won't be comparing against such large inputs short-term. The larger strings (fragments) are copied verbatim, and not compared against---but they _were_ prior to the previous commit that stopped unencoding and re-encoding. So: Rust built-ins for inputs that are expected to be small.
* tamer: Remove default SymbolIndex (et al) index typeMike Gerwitz2021-07-291-0/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Oh boy. What a mess of a change. This demonstrates some significant issues we have with Symbol. I had originally modelled the system a bit after Rustc's, but deviated in certain regards: 1. This has a confurable base type to enable better packing without bit twiddling and potentially unsafe tricks I'd rather avoid unless necessary; and 2. The lifetime is not static, and there is no global, singleton interner; and 3. I pass around references to a Symbol rather than passing around an index into an interner. For #3---this is done because there's no singleton interner and therefore resolving a symbol requires a direct reference to an available interner. It also wasn't clear to me (and still isn't, in fact) whether more than one interner may be used for different contexts. But, that doesn't preclude removing lifetimes and just passing around indexes; in fact, I plan to do this in the frontend where the parser and such will have direct interner access and can therefore just look up based on a symbol index. We could reserve references for situations where exposing an interner would be undesirable. Anyway, more to come...
* tamer: Cargo.lock: Dependency updatesMike Gerwitz2021-06-211-123/+118
| | | | This project has been on pause for over a year.
* [DEV-7504] Add GraphML generationJoseph Frazer2020-05-131-0/+17
| | | | | | | | We want to be able to build a representation of the dependency graph so we can easily inspect it. We do not want to make GraphML by default. It is better to use a tool. We use "petgraph-graphml".
* TAMER: Update Cargo dependenciesMike Gerwitz2020-04-291-58/+60
* ir::asg::Object::Empty: Remove variantMike Gerwitz2020-03-191-0/+1
| | | | | | | | | | | | | | | | | | | | | This variant is unnecessary, as it was used only by the indexer to represent the absence of a node, for which was can simply use `None` in the containing `Option`. * tamer/Cargo.toml: Add `lazy_static`. * tamer/Cargo.lock: Update. * tamer/src/ir/asg/base.rs (with_capacity): Use `None` in place of `Some(Object::Empty)`. * tamer/src/ir/asg/object.rs: Adjust state machine graphic. (Empty): Remove variant. (Missing): Remove reference to variance. * tamer/src/lib.rs: Import `lazy_static` for test builds. * tamer/obj/xmle/writer/writer.rs (Section::iter): Remove `Object::Empty` from documentation. (test::): Remove references to `Object::Missing`. `lazy_static!` used here. * tamer/obj/xmle/writer/xmle.rs (test::write_section_catch_missing): Replace reference to `Object::Missing`.
* [DEV-7081] Add options to tameldJoseph Frazer2020-03-061-0/+238
| | | | | | | We want to add an option to set the output file to the linker so we do not need to redirect output to awk any longer. This also adds integration tests for tameld.
* TAMER: Arena-based string internerMike Gerwitz2020-02-241-0/+7
| | | | | | | | | | | | | | | | | | Contrary to what I said previously, this replaces the previous implementation with an arena-backed internment system. The motivation for this change was investigating how Rustc performed its string interning, and why they chose to associate integer identifiers with symbols. The intent was originally to use Rustc's arena allocator directly, but that create pulled in far too many dependencies and depended on nightly Rust. Bumpalo provides a very similar implementation to Rustc's DroplessArena, so I went with that instead. Rustc also relies on a global, singleton interner. I do not do that here. Instead, the returned Symbol carries a lifetime of the underlying arena, as well as a pointer to the interned string. Now that this is put to rest, it's time to move on.
* tamer::sym: FNV => Fx HashMike Gerwitz2020-02-241-4/+13
| | | | | | | | | | | | | | | | | | | | | | | | For strings of any notable length, Fx Hash outperforms FNV. Rustc also moved to this hash function and noticed performance improvements. Fortunately, as was accounted for in the design, this was a trivial switch. Here are some benchmarks to back up that claim: test hash_set::fnv::with_all_new_1000 ... bench: 133,096 ns/iter (+/- 1,430) test hash_set::fnv::with_all_new_1000_with_capacity ... bench: 82,591 ns/iter (+/- 592) test hash_set::fnv::with_all_new_rc_str_1000_baseline ... bench: 162,073 ns/iter (+/- 1,277) test hash_set::fnv::with_one_new_1000 ... bench: 37,334 ns/iter (+/- 256) test hash_set::fnv::with_one_new_rc_str_1000_baseline ... bench: 18,263 ns/iter (+/- 261) test hash_set::fx::with_all_new_1000 ... bench: 85,217 ns/iter (+/- 1,111) test hash_set::fx::with_all_new_1000_with_capacity ... bench: 59,383 ns/iter (+/- 752) test hash_set::fx::with_all_new_rc_str_1000_baseline ... bench: 98,802 ns/iter (+/- 1,117) test hash_set::fx::with_one_new_1000 ... bench: 42,484 ns/iter (+/- 1,239) test hash_set::fx::with_one_new_rc_str_1000_baseline ... bench: 15,000 ns/iter (+/- 233) test hash_set::with_all_new_1000 ... bench: 137,645 ns/iter (+/- 1,186) test hash_set::with_all_new_rc_str_1000_baseline ... bench: 163,129 ns/iter (+/- 1,725) test hash_set::with_one_new_1000 ... bench: 59,051 ns/iter (+/- 1,202) test hash_set::with_one_new_rc_str_1000_baseline ... bench: 37,986 ns/iter (+/- 771)
* TAMER: Initial string interning abstractionMike Gerwitz2020-02-241-0/+7
| | | | | | | | | | | | | | | | | | | | | | | This is missing two key things that I'll add shortly: a HashMap-based one for use in the ASG for node mapping, and an entry-based system for manipulations. This has been a nice start for exploring various aspects of Rust development, as well as conventions that I'd like to implement. In particular: - Robust documentation intended to guide people through learning the necessary material about the compiler, as well as related work to rationalize design decisions; - Benchmarks; - TDD; - And just getting used to Rust in general. I've beat this one to death, so I'll commit this and make smaller changes going forward to show how easily it can evolve. (This module was originally named `intern` but this commit and those that follow rewrote it to `sym`.)
* Graph-based POCMike Gerwitz2019-12-021-0/+1
| | | | | | This makes use of Petgraph for representing the dependency graph and uses a separate data structure for both string interning and indexing by symbol name.
* Cargo.toml: Add petgraphMike Gerwitz2019-12-021-0/+23
| | | | This will be used to represent the dependency graph.
* tamer/Cargo.toml: Add quick_xmlMike Gerwitz2019-11-271-0/+19
* TAMER: Initial commitMike Gerwitz2019-11-181-0/+6