5 ms·

> tsc depends on shared mutability and has a cyclical mutable reference. Rust is designed to prevent this behavior. Having two references to the same data (sha

by jupp0r 5y ago

> tsc depends on shared mutability and has a cyclical mutable reference. Rust is designed to prevent this behavior. Having two references to the same data (shared mutability) is undefined behavior in Rust. This problem has numerous solutions in Rust - (A)Rc, RefCell etc. I don't understand how this caused the author of the article to stop considering Rust.

petmon 5y ago
Non-GC languages are bad in general at handling cyclical references (mutable or not), and Rust is especially ill suited for it because of the borrow checker. For example should an arbitrary reference in tsc become an rc::Rc or an rc::Weak? You have to tease out the implicit ownership model and one may not even exist. tsc was designed expecting GC and it makes perfect sense to port it to another fast GC language.
- throw10920 5y ago
  I'm not a Rust fanboy (in fact, I rather despise the RESF, especially given Rust's mediocre tooling), but: I think that "You have to tease out the implicit ownership model and one may not even exist" suggests a problem with the program itself. I can't think of any reason why a program must have an ill-formed ownership model (unlike, say, the fact that many interesting programs must have an embedded dynamic type system (tagged unions etc) to do their thing). Now. The Rust language and existing tooling doesn't give you any help in figuring out the ownership model, but I can easily imagine a language and tools that would help with that. This isn't meant to refute anything you've said (you said "[existing] non-GC languages are bad in general" not that non-GC languages cannot be good) - just add clarity.
  - adamnemecek 5y ago
    > I rather despise the RESF, especially given Rust's mediocre tooling Which tooling are you talking about?
    - throw10920 5y ago
      Copying from a previous comment[1]: The Rust compiler is both dog-slow and massive (both from a source and binaries perspective), and doesn't have a working incremental compilation mode yet, or support in-process hot-patching. There's no Rust REPL (hacks like papyrus don't count). Poor structural editing support. Integration with various editors/IDEs is lacking (e.g. there's no support for reporting possible performance issues with code constructs in any editor that I'm aware of, nor is there in-editor per-function disassembly or LLVM IR inspection, or borrow-checker lifetime annotation, no extract-function refactoring). [1] https://news.ycombinator.com/item?id=29925783 https://news.ycombinator.com/item?id=29925783
      - adamnemecek 5y ago
        The compiler is relatively fast for recompilation but you are right, this is a problem that's actively being worked on. > support in-process hot-patching I assume that we are comparing this with say C++ compilers. I think that Visual Studio added this recently but idk if saying this is a valid criticism of the compiler. > There's no Rust REPL Are you comparing it with C++ compilers? The Rust tooling is so much better than C++ tooling that it's not even funny. You are right, there are places where this could be improved but just cargo makes my life so so so much easier than any other package manager.
        throw10920 5y ago
        > The compiler is relatively fast for recompilation Relative to Rust when doing a cold-compile, maybe, but certainly not relative to other languages like C, sane C++, Go, or Common Lisp. I'm comparing Rust tooling with existing tooling in other languages in general, that is feasible to implement. Common Lisp has multiple compilers (SBCL, Allegro, Clasp) that compile code nearly instantly (within a second for my modest 2kloc codebases, and individual functions in milliseconds), have REPLs (that also do native-code compilation under the hood using the compiler proper - no hacks), and support hotpatching. Visual Studio implements in-process hot-patching, too, so between C++'s highly static nature, and the fact that SBCL is run by a tiny group of unpaid contributors, there's no reason for the Rust compiler to not have it. Meanwhile, GHC (compiling Haskell, a statically-typed language) has a REPL, so it's clear that being dynamically-typed is not a requirement. From a user's perspective, having either long compilation times or lacking a REPL is OK, but not having either is unacceptable. Having a good package manager is necessary for having good tooling, but not sufficient.
  - bcrosby95 5y ago
    A program doesn't have to have an ill-formed ownership model. But if it does and you're trying to translate from one language to another, you should probably pick the language that makes the job easier. It reminds me of a programming assignment I had 20 years ago. We had to take our teacher's old FORTRAN program and "convert" it to Java or C++. I knew both equally well at the time - and I picked C++ because it had goto whereas Java didn't. This meant that I didn't really have to unravel the meaning of the program. Whereas with Java, I would have to.
  - deleted 5y ago
    [deleted]
  - klodolph 5y ago
    Speaking as someone who has written non-trivial compilers in both Rust and Go... Compilers tend to use a bit thornier data structures and graphs than you might see in other realms. It is very convenient to just represent these graphs as objects connected by pointers, and know that you don't have to worry about objects that become unreachable. For example, the values in an SSA-based IR are all full of pointers to other values. Each value represents the computation to produce that value, like "x12 / 4". A strength-reduction pass goes in and mutates this node, replacing it with "x12 >> 2" (if such a change is valid). It knows the change is valid because it follows pointers from the node to its inputs. The change is available to all upstream values immediately because it is mutated. These changes may make other values unreachable, at which point, you don't care about them. You only care about the values which are reachable from computations with side effects. These nodes definitely have cycles and IMO, the notion of weak references between them doesn't make sense. I'm sure there's a way to do that in Rust. Please, nobody try to explain how. I could figure it out. The thing is... it's not obvious how to do it in Rust, and figuring out how to "explain ownership to the Rust compiler" without creating Rc<RefCell<T>> cycle leaks is a non-trivial task that sucks away time I could be spending writing the compiler. This reminds me of a paper I saw go by years back about writing a compiler in Haskell. Pure Haskell code doesn't let you mutate objects and doesn't let you do pointer comparisons, so it creates problems if you're trying to implement an algorithm which is conceptually pure (at a high level, a function with inputs and outputs) but where you're taking the implementation from a paper which constructs the output iteratively, piece by piece. The problem is that your data structures have to be annotated to show which parts are mutable (IORef, STRef, or TVar), but "which parts are mutable" may have a different answer depending on whether you are inside some function transforming or constructing a data structure. It was obvious to me, reading the paper, that while I love functional purity, and functional purity solves all sorts of problems and makes it easier to write code in general, it sometimes gets in the way of getting shit done. The same is true of Rust's notion of ownership... super useful when it lets me write fast, efficient code without having to think about ownership (when it just works and gets out of the way), and super annoying when you have to figure out how to explain your program to Rust.
    - throw10920 5y ago
      Thank you for explaining - now that you've pointed it out, I can see that this is just another form of the "graphs are hard in Rust" problem that I've encountered before. However, I still stand by my point - Rust might be bad at graphs, but I believe that a well-designed language with a borrow checker (maybe something closer to Lobster, which automatically inserts RC cells when you try to multiply mutable borrow[1] - something obviously more correct than what Rust does, I'm not sure how they messed that one up) wouldn't necessarily have to be. [1] https://aardappel.github.io/lobster/memory_management.html https://aardappel.github.io/lobster/memory_management.html
  - chubot 5y ago
    If your program is an interpreter, then I think the ownership model is going to be dominated by the program being interpreted, not the intepreter itself... That is, has to be general enough to interpret any program, and many of those programs will have cyclic data structures. TSC is not an interpreter, but its type system is Turing complete, so I wouldn't be surprised if it has some similar issues.
- sealeck 5y ago
  Rust does have a third-party `Gc` type (which used to be in the stdlib).
  - cztomsik 5y ago
    Is that the one where you need to derive() for every struct you want to use and which is, in general, not compatible with the rest of rust ecosystem?
- armchairhacker 5y ago
  I honestly like the explicit weak ref model and it’s usually trivial (child objects are strong references, parents and siblings are weak), and rust has Gc as a last resort. But if the author’s more familiar with Go, performance in Go is likely good enough
- deleted 5y ago
  [deleted]
speedgoose 5y ago
I think the point is valid. As a rust beginner I tried to make a graph data structure and it was difficult. Using RefCell is not very nice because it moves the problem from compile time to runtime and you still can’t mutate the same data structure more than once at the same time.
- tomcam 5y ago
  This is interesting but I don't know Rust. Presumably your graph data structure grows dynamically, meaning you have to add nodes at runtime. When. you say you can't mutate the same data structure more than once at runtime, what does it mean? That you can't set both a parent and a child pointer in the same function, or what?
  - deleted 5y ago
    [deleted]
  - deleted 5y ago
    [deleted]
  - speedgoose 5y ago
    I’m very far from being a rust expert but it was difficult to build a bi-directional graph because it’s difficult to connect the nodes together. A simple recursive algorithm will not work. I ended up using a crate. I found the following article interesting on the topic : https://aminb.gitbooks.io/rust-for-c/content/graphs/ https://aminb.gitbooks.io/rust-for-c/content/graphs/
    - jupp0r 5y ago
      It shouldn't be difficult: 1. You have a graph struct that has ownership of all nodes (in Rc containers). 2. Nodes have Weak references to connected nodes
  - bobbylarrybobby 5y ago
    In the case of RefCell, when you begin modifying its data, you’re not allowed to begin modifying its data a second time without declaring “I’m done” with the first modification. This makes doing several modifications in different places that are interspersed with each other tricky because it’s hard to reason about when each spot is actually done so that a modification can be performed elsewhere. (If your program is single threaded it’s possible you don’t even care about mutation happening in multiple places, but Rust cares because in general Rust programs need not be single threaded.)
slaymaker1907 5y ago
While I hate Go and love Rust, there is also the issue that RefCell/Gc/Rc are very different in terms of how expensive a memory allocation is compared to node. Historically there were very similar problems in trying to write C++ like one would write Java. Memory allocators today are much better and closer to GC languages, but I suspect it will still be more expensive for very allocation heavy code. One way you could get this to work at the cost of some safety (depending on how you do it) would be to use arena style allocation. Obviously there are ways to do this safely in Rust, but it is probably easier to do it unsafely for a port. However, if you just use a high performance language with a GC like Go/C#/Java, the port will be easier and you won't have to worry about doing too many allocations.

by jupp0r 5y ago

petmon 5y ago

Non-GC languages are bad in general at handling cyclical references (mutable or not), and Rust is especially ill suited for it because of the borrow checker. For example should an arbitrary reference in tsc become an rc::Rc or an rc::Weak? You have to tease out the implicit ownership model and one may not even exist. tsc was designed expecting GC and it makes perfect sense to port it to another fast GC language.

throw10920 5y ago
I'm not a Rust fanboy (in fact, I rather despise the RESF, especially given Rust's mediocre tooling), but: I think that "You have to tease out the implicit ownership model and one may not even exist" suggests a problem with the program itself. I can't think of any reason why a program must have an ill-formed ownership model (unlike, say, the fact that many interesting programs must have an embedded dynamic type system (tagged unions etc) to do their thing). Now. The Rust language and existing tooling doesn't give you any help in figuring out the ownership model, but I can easily imagine a language and tools that would help with that. This isn't meant to refute anything you've said (you said "[existing] non-GC languages are bad in general" not that non-GC languages cannot be good) - just add clarity.
- adamnemecek 5y ago
  > I rather despise the RESF, especially given Rust's mediocre tooling Which tooling are you talking about?
  - throw10920 5y ago
    Copying from a previous comment[1]: The Rust compiler is both dog-slow and massive (both from a source and binaries perspective), and doesn't have a working incremental compilation mode yet, or support in-process hot-patching. There's no Rust REPL (hacks like papyrus don't count). Poor structural editing support. Integration with various editors/IDEs is lacking (e.g. there's no support for reporting possible performance issues with code constructs in any editor that I'm aware of, nor is there in-editor per-function disassembly or LLVM IR inspection, or borrow-checker lifetime annotation, no extract-function refactoring). [1] https://news.ycombinator.com/item?id=29925783 https://news.ycombinator.com/item?id=29925783
    - adamnemecek 5y ago
      The compiler is relatively fast for recompilation but you are right, this is a problem that's actively being worked on. > support in-process hot-patching I assume that we are comparing this with say C++ compilers. I think that Visual Studio added this recently but idk if saying this is a valid criticism of the compiler. > There's no Rust REPL Are you comparing it with C++ compilers? The Rust tooling is so much better than C++ tooling that it's not even funny. You are right, there are places where this could be improved but just cargo makes my life so so so much easier than any other package manager.
      - throw10920 5y ago
        > The compiler is relatively fast for recompilation Relative to Rust when doing a cold-compile, maybe, but certainly not relative to other languages like C, sane C++, Go, or Common Lisp. I'm comparing Rust tooling with existing tooling in other languages in general, that is feasible to implement. Common Lisp has multiple compilers (SBCL, Allegro, Clasp) that compile code nearly instantly (within a second for my modest 2kloc codebases, and individual functions in milliseconds), have REPLs (that also do native-code compilation under the hood using the compiler proper - no hacks), and support hotpatching. Visual Studio implements in-process hot-patching, too, so between C++'s highly static nature, and the fact that SBCL is run by a tiny group of unpaid contributors, there's no reason for the Rust compiler to not have it. Meanwhile, GHC (compiling Haskell, a statically-typed language) has a REPL, so it's clear that being dynamically-typed is not a requirement. From a user's perspective, having either long compilation times or lacking a REPL is OK, but not having either is unacceptable. Having a good package manager is necessary for having good tooling, but not sufficient.
- bcrosby95 5y ago
  A program doesn't have to have an ill-formed ownership model. But if it does and you're trying to translate from one language to another, you should probably pick the language that makes the job easier. It reminds me of a programming assignment I had 20 years ago. We had to take our teacher's old FORTRAN program and "convert" it to Java or C++. I knew both equally well at the time - and I picked C++ because it had goto whereas Java didn't. This meant that I didn't really have to unravel the meaning of the program. Whereas with Java, I would have to.
- deleted 5y ago
  [deleted]
- klodolph 5y ago
  Speaking as someone who has written non-trivial compilers in both Rust and Go... Compilers tend to use a bit thornier data structures and graphs than you might see in other realms. It is very convenient to just represent these graphs as objects connected by pointers, and know that you don't have to worry about objects that become unreachable. For example, the values in an SSA-based IR are all full of pointers to other values. Each value represents the computation to produce that value, like "x12 / 4". A strength-reduction pass goes in and mutates this node, replacing it with "x12 >> 2" (if such a change is valid). It knows the change is valid because it follows pointers from the node to its inputs. The change is available to all upstream values immediately because it is mutated. These changes may make other values unreachable, at which point, you don't care about them. You only care about the values which are reachable from computations with side effects. These nodes definitely have cycles and IMO, the notion of weak references between them doesn't make sense. I'm sure there's a way to do that in Rust. Please, nobody try to explain how. I could figure it out. The thing is... it's not obvious how to do it in Rust, and figuring out how to "explain ownership to the Rust compiler" without creating Rc<RefCell<T>> cycle leaks is a non-trivial task that sucks away time I could be spending writing the compiler. This reminds me of a paper I saw go by years back about writing a compiler in Haskell. Pure Haskell code doesn't let you mutate objects and doesn't let you do pointer comparisons, so it creates problems if you're trying to implement an algorithm which is conceptually pure (at a high level, a function with inputs and outputs) but where you're taking the implementation from a paper which constructs the output iteratively, piece by piece. The problem is that your data structures have to be annotated to show which parts are mutable (IORef, STRef, or TVar), but "which parts are mutable" may have a different answer depending on whether you are inside some function transforming or constructing a data structure. It was obvious to me, reading the paper, that while I love functional purity, and functional purity solves all sorts of problems and makes it easier to write code in general, it sometimes gets in the way of getting shit done. The same is true of Rust's notion of ownership... super useful when it lets me write fast, efficient code without having to think about ownership (when it just works and gets out of the way), and super annoying when you have to figure out how to explain your program to Rust.
  - throw10920 5y ago
    Thank you for explaining - now that you've pointed it out, I can see that this is just another form of the "graphs are hard in Rust" problem that I've encountered before. However, I still stand by my point - Rust might be bad at graphs, but I believe that a well-designed language with a borrow checker (maybe something closer to Lobster, which automatically inserts RC cells when you try to multiply mutable borrow[1] - something obviously more correct than what Rust does, I'm not sure how they messed that one up) wouldn't necessarily have to be. [1] https://aardappel.github.io/lobster/memory_management.html https://aardappel.github.io/lobster/memory_management.html
- chubot 5y ago
  If your program is an interpreter, then I think the ownership model is going to be dominated by the program being interpreted, not the intepreter itself... That is, has to be general enough to interpret any program, and many of those programs will have cyclic data structures. TSC is not an interpreter, but its type system is Turing complete, so I wouldn't be surprised if it has some similar issues.
sealeck 5y ago
Rust does have a third-party `Gc` type (which used to be in the stdlib).
- cztomsik 5y ago
  Is that the one where you need to derive() for every struct you want to use and which is, in general, not compatible with the rest of rust ecosystem?
armchairhacker 5y ago
I honestly like the explicit weak ref model and it’s usually trivial (child objects are strong references, parents and siblings are weak), and rust has Gc as a last resort. But if the author’s more familiar with Go, performance in Go is likely good enough
deleted 5y ago
[deleted]

speedgoose 5y ago

I think the point is valid. As a rust beginner I tried to make a graph data structure and it was difficult. Using RefCell is not very nice because it moves the problem from compile time to runtime and you still can’t mutate the same data structure more than once at the same time.

tomcam 5y ago
This is interesting but I don't know Rust. Presumably your graph data structure grows dynamically, meaning you have to add nodes at runtime. When. you say you can't mutate the same data structure more than once at runtime, what does it mean? That you can't set both a parent and a child pointer in the same function, or what?
- deleted 5y ago
  [deleted]
- deleted 5y ago
  [deleted]
- speedgoose 5y ago
  I’m very far from being a rust expert but it was difficult to build a bi-directional graph because it’s difficult to connect the nodes together. A simple recursive algorithm will not work. I ended up using a crate. I found the following article interesting on the topic : https://aminb.gitbooks.io/rust-for-c/content/graphs/ https://aminb.gitbooks.io/rust-for-c/content/graphs/
  - jupp0r 5y ago
    It shouldn't be difficult: 1. You have a graph struct that has ownership of all nodes (in Rc containers). 2. Nodes have Weak references to connected nodes
- bobbylarrybobby 5y ago
  In the case of RefCell, when you begin modifying its data, you’re not allowed to begin modifying its data a second time without declaring “I’m done” with the first modification. This makes doing several modifications in different places that are interspersed with each other tricky because it’s hard to reason about when each spot is actually done so that a modification can be performed elsewhere. (If your program is single threaded it’s possible you don’t even care about mutation happening in multiple places, but Rust cares because in general Rust programs need not be single threaded.)

slaymaker1907 5y ago

While I hate Go and love Rust, there is also the issue that RefCell/Gc/Rc are very different in terms of how expensive a memory allocation is compared to node. Historically there were very similar problems in trying to write C++ like one would write Java. Memory allocators today are much better and closer to GC languages, but I suspect it will still be more expensive for very allocation heavy code. One way you could get this to work at the cost of some safety (depending on how you do it) would be to use arena style allocation. Obviously there are ways to do this safely in Rust, but it is probably easier to do it unsafely for a port. However, if you just use a high performance language with a GC like Go/C#/Java, the port will be easier and you won't have to worry about doing too many allocations.