Git implemented in Rust • Hacker News Board

Re: Git implemented in Rust

#101

Post by beatgammit » Mon, Apr 01, 2019, 6:22 PM UTC

mises wrote: post #68

Can somebody tell me what is behind the recent rewrite-all-the-things-in-rust craze? I get it can have some benefits in terms of security, but it seems rewriting so many things in it just for the sake of it is a bit excessive. I understand some of these are very likely for educational purposes (like this one and others; it's good for getting more familiar with the language), but it still seems to be a bit of a strang…

For me, dealing with something written in Rust is less painful than dealing with something with bindings for Rust, and honestly I'd consider rewriting something for that reason. And that's the case for nearly any language.

For example, I rewrote `tar` in JavaScript because I wanted to use it in the browser, and I didn't want to fiddle with trying to compile the existing project to JS. It took me a weekend and it worked pretty well for the project I needed it for. That project has since died (completely redesigned), but the tar stuff still works.

These days I'm getting lazy, so for something like git, I'll often exec out to the CLI app instead of fiddling with bindings, especially if it's not a performance-critical part of my app. However, I'd definitely look for a rewrite first and clean bindings second to use as a lib, especially if the rewrite had a suitable license (anything not copyleft).

Re: Git implemented in Rust

#102

Post by steveklabnik » Mon, Apr 01, 2019, 6:29 PM UTC

beatgammit wrote: post #100

jchw wrote: post #83

Earlier quoted context omitted.

I scrolled down for this comment. Actually there's a lot of great reasons to rewrite everything in every language. Git is an especially good piece of software to implement everywhere because it's relatively stable and it's pretty useful. As for actual reasons, one good example is so you can keep your dependencies in the language, using the language package manager. For Go nobody even questions that this is worth it;…

Also, it would be pretty sweet to use git with Redox, and I don't think Redox works very well with things not written in Rust.

Redox can run a lot of non-Rust software, see https://www.redox-os.org/news/release-0.5.0/ a list of packages that work.

Re: Git implemented in Rust

#103

Post by SilasX » Mon, Apr 01, 2019, 7:15 PM UTC

What's with all those posts about "X implemented in Rust" today?

Re: Git implemented in Rust

#104

Post by littlestymaar » Mon, Apr 01, 2019, 7:26 PM UTC

taktoa wrote: post #77

abhijat wrote: post #76

Earlier quoted context omitted.

Thanks, I bought the book. Still undecided as to which language to work in, I wanted to use rust but the one part I'm unsure about is possibly where tree like data structures will need to be implemented? I guess that's tough to do in rust? I will give it a try.

Trees are easy in Rust. It's graphs that are harder.

Git “trees” are graphs though, since you have merge commits.

Re: Git implemented in Rust

#105

Post by skybrian » Mon, Apr 01, 2019, 8:36 PM UTC

Twisol wrote: post #81

abhijat wrote: post #76

Earlier quoted context omitted.

Thanks, I bought the book. Still undecided as to which language to work in, I wanted to use rust but the one part I'm unsure about is possibly where tree like data structures will need to be implemented? I guess that's tough to do in rust? I will give it a try.

Graphs are harder if you try to use pointers to identify neighbors. In Rust, a pointer is not merely an index into memory; it is a statement and guarantee about how that memory will be accessed. These semantics are more than a graph structure needs. To "get around" this (but see the next paragraph), we usually associate each node to a simple identifier such as an integer (usize), and store all nodes into a Vec. Neigh…

There are benefits but they come with downsides: you can have node ids pointing to deleted nodes, and collecting unused nodes is up to you. If you want to avoid fragmentation, you need to recycle nodes and possibly node ids as well. These are things garbage collectors handle.

It's not all that different from a database, though.

Re: Git implemented in Rust

#106

Post by e12e » Mon, Apr 01, 2019, 8:46 PM UTC

hannob wrote: post #2

I don't see any info about a license. Strongly recommend using some standard FOSS license before plenty of people add commits and it gets a big mess clearing up the licensing situation later.

Fwiw license (mit) has been added in the past 7 hour: https://github.com/chrisdickinson/git-rs/commit/2be8314b9b1c...

Re: Git implemented in Rust

#107

Post by steveklabnik » Mon, Apr 01, 2019, 10:22 PM UTC

skybrian wrote: post #105

Twisol wrote: post #81

Earlier quoted context omitted.

Graphs are harder if you try to use pointers to identify neighbors. In Rust, a pointer is not merely an index into memory; it is a statement and guarantee about how that memory will be accessed. These semantics are more than a graph structure needs. To "get around" this (but see the next paragraph), we usually associate each node to a simple identifier such as an integer (usize), and store all nodes into a Vec. Neigh…

There are benefits but they come with downsides: you can have node ids pointing to deleted nodes, and collecting unused nodes is up to you. If you want to avoid fragmentation, you need to recycle nodes and possibly node ids as well. These are things garbage collectors handle. It's not all that different from a database, though.

Recycling IDs is pretty easy with generational indices.

Re: Git implemented in Rust

#108

Post by aidenn0 » Mon, Apr 01, 2019, 11:03 PM UTC

_bxg1 wrote: post #90

aidenn0 wrote: post #87

Earlier quoted context omitted.

Actually any high performance GC'd languages would be fine too because latency is a non-issue for long running git operations (you won't notice if your git clone pauses for 100ms, whereas you will notice if your UI does). Throughput of malloc() and GCd languages tends to be similar when latency isn't a concern.

I was speaking more to stability. Rust is designed to be an incredibly safe language without sacrificing any performance; that seems like a good match for a version-control system.

Most GC'd languages are also memory safe.

Re: Git implemented in Rust

#109

Post by Twisol » Tue, Apr 02, 2019, 12:22 AM UTC

skybrian wrote: post #105

Twisol wrote: post #81

Earlier quoted context omitted.

Graphs are harder if you try to use pointers to identify neighbors. In Rust, a pointer is not merely an index into memory; it is a statement and guarantee about how that memory will be accessed. These semantics are more than a graph structure needs. To "get around" this (but see the next paragraph), we usually associate each node to a simple identifier such as an integer (usize), and store all nodes into a Vec. Neigh…

There are benefits but they come with downsides: you can have node ids pointing to deleted nodes, and collecting unused nodes is up to you. If you want to avoid fragmentation, you need to recycle nodes and possibly node ids as well. These are things garbage collectors handle. It's not all that different from a database, though.

> It's not all that different from a database, though.

Indeed! I'm tempted to coin a variant of Greenspun's Tenth Rule: any sufficiently complicated program contains an ad-hoc, informally specified, bug-ridden, incomplete implementation of a database engine.

> There are benefits but they come with downsides

Downsides relative to what? The downsides listed are all in common with traditional pointer-based references, so I would argue that garbage collection is rather orthogonal to the question of storing indices instead of pointers. Any allocation comes out of a memory arena of some kind, be it an explicit vector of slots or the implicitly-defined standard heap. The tools for solving these problems are the same in all cases.

Certainly, Rust's references avoid all of the problems you listed. Rust pointers essentially embed the semantics of a garbage collector at compile-time [0], in the domain where ownership patterns can be strictly verified. But nodes within a graph are already a poor fit for the ownership model -- the entity that "owns" a node is really the graph itself, not its neighbors -- so that's the level of granularity at which Rust's references are useful. You need something else within the scope of the graph.

EDIT: On reflection, you might be referring to a language like Java which has an ambient global garbage collector. Indeed, using indices instead of pointers means you're on your own -- you've allocated the memory arena through the standard means, but then you take on the responsibility of managing that memory yourself. This is a fair criticism! Purely in my experience, data modeled as a loose graph of directly-related objects is a lot more difficult to understand and maintain than data modeled indirectly using some form of identifier -- mostly because of the effects I mentioned in my earlier post on associating new information to an entity.

[0] https://words.steveklabnik.com/borrow-checking-escape-analys...

Re: Git implemented in Rust

#110

Post by skybrian » Tue, Apr 02, 2019, 12:53 AM UTC

Twisol wrote: post #109

skybrian wrote: post #105

Earlier quoted context omitted.

There are benefits but they come with downsides: you can have node ids pointing to deleted nodes, and collecting unused nodes is up to you. If you want to avoid fragmentation, you need to recycle nodes and possibly node ids as well. These are things garbage collectors handle. It's not all that different from a database, though.

> It's not all that different from a database, though. Indeed! I'm tempted to coin a variant of Greenspun's Tenth Rule: any sufficiently complicated program contains an ad-hoc, informally specified, bug-ridden, incomplete implementation of a database engine. > There are benefits but they come with downsides Downsides relative to what? The downsides listed are all in common with traditional pointer-based references, s…

Yes, that's what I meant. Cleaning up unreferenced nodes (should you want to do that) would require some kind of mini-garbage collection algorithm. And indeed, git has a gc command to do this, even though reference counting would work for a DAG. It's doable, but it's not what I'd call simple.

But if you know through some other means the exact time when a node should be deleted, you can delete it at that time, and anyone following a soft reference will find that it's no longer there, which may be a way of catching a bug. This is how both databases and entity component systems work. But it does mean that resolving a reference can fail, and you have to handle that somehow.