I always find it funny when people propose adding closures to C. Because the moment you add closures (in the way most languages implement them, not Rust's implementation), you're adding automatic boxing, which implies garbage collection and a runtime. Which basically means you've added objects. Which...sure you could do, but at that point, you're not adding to C, you're just making a new language.
typeof is supported by everything[1] except the C standard. It was rejected in the 1990s and nobody on the committee seems to want to revisit the decision.
To be fair, typeof is not as useful without statement expressions (`({ ... })`), and statement expressions aren't as widely supported.
[1] All the major compilers support it (clang, GCC, IBM, Intel, Microsoft, Solaris, etc), plus or minus underscores in the identifier.
C++ closures are a bit weird in that you have to specify how the captured data needs to be captured (either by reference or by copy). How the data is handled also depends on the implementation of std::function (if you decide to wrap your lambdas in that). It's possible that the implementation for std::function actually makes a reference-counted heap allocation every time a new closure is created. Anyway, the result is a lot of complexity that would be impossible to shoe-horn into C.
Should be able to do it without refcounting if you wanted to go even more minimal, too. Make a call to copy the storage, and another one to destroy it. Then the user can use whatever lifetime management they already use for other things.
> Because the moment you add closures (in the way most languages implement them, not Rust's implementation), you're adding automatic boxing, which implies garbage collection and a runtime.
Isn't it possible to avoid the whole slippery slope by capturing objects by value?
Sure, unless your value objects contain references. Then you’re looking at a deep copy, which can be expensive and/or very application-specific. It’s hard to do copy by value generically.
References in C are implemented by pointers, which can be copied very easily. The trouble is with properly cleaning up when the closure isn't needed anymore, but that problem already exists when you copy pointers explicitly.
I don't see how that's relevant. If a developer sets a pointer to point to a stack object then copying the pointer, whether manually or through a hypothetical closure, doesn't change nor create the problem.
It isn't. The hypothetical problem was setting a pointer to a stack variable. That's a no-no from the start, and adding hypothetical closures to the mix changes nothing.
> Right, so your original claim about properly cleaning up is not the only problem with closures in C.
Your comment makes no sense. OP stated that your hypothetical problem isn't even a problem if the developer knows what he is doing, and your take from that is that there are more problems?
The original poster said the trouble was cleaning up after the closure is no longer needed. That's clearly not the case as this thread has covered. I thought the previous poster was the original poster, so just replace "your original claim" with "the original claim".
I'd like to see that ample evidence. On the contrary, I know even fairly experienced developers who get burned with memory issues in C - and I have never ever heard of even the most junior developer to have any problem with double frees in Java :)
Plus..... even if you could do that, WHY? C is a simple language, close to the "metal". If you want a language that has every-feature-and-their-mother, and can be close to the metal when needed, and can be used to blow both your feet off, just use C++.
Adding functional closures to C is somewhat akin to adding "asm" and "volatile" in Haskell.... even if you could do it, why would you? It just breaks the very essence of the language.
> Sure, unless your value objects contain references.
As others have already pointed out, C does not have references. It does however have pointers, and pointers are already copied by value.
> Then you’re looking at a deep copy
There is no such thing in standard C. Objects are copied by value, including pointers, and if you want to "deep copy" your custom data structures then you need to implement your custom cloning routines. However, naturally your custom cloning functions wouldn't be used directly to capture any variable.
> which can be expensive and/or very application-specific.
That's hardly specific to C.
> It’s hard to do copy by value generically.
Actually, it isn't. In fact with C it's quite trivial, and perhaps as trivial as it gets. There's no garbage collection thingy, no RAII, no deep copies, no refcounting... nothing. Just plain memcpy() from one object to another. That's it.
if that meets the semantics of what you’re trying to do, great. but often in programming it’s not. the depth of the copy you want depends on what you’re trying to do. copying pointers (or references, or whatever might point to dynamically allocated memory) by value means using a garbage collector or reference counting mechanism, or risk a memory leak.
If you think being specific about what you want copied, freeing only when you know it's appropriate, and tracking any metadata around that yourself if a problem, don't work in C.
Get it right or risk a memory leak is the name of the game.
It’s your program. The suggestion was that copy-everything-by-value solves the closure/memory issue with respect to copies. It does not. This is also why C doesn’t have closures. Ships passing in the night...
No, it's the C programming language. It has been like that since the 70s, and lots of people have been using it to develop high availability software for decades.
Just because some people never learned its basics nor are familiar with the subject that doesn't mean they have a point.
> The suggestion was that copy-everything-by-value solves the closure/memory issue with respect to copies.
No, that's quite wrong. The suggestion was thay passing objects by value would enable capturing variables without any of the slippery slope nonsense that was pointed out.
> This is also why C doesn’t have closures.
No, that's quite wrong as well. C doesn't have closures because no one bothered to add them, which is the exact same reason why C doesn't have namespaces or generics or any other feature ever. That's it.
I meant the Box type itself. In C++, std::string and std::function are usually intentionally padded, so that when the data is small enough, it can fit inside the object itself, rather than storing the pointer to heap-allocated storage.
A Box'd Fn is two pointers: one to the code, and one to the data. The only way that this would work is if the data was a single usize, which is not likely to be many useful closures. In theory it could happen, I guess...
The idea is that you intentionally pad your type with fields that don't do anything other than provide a scratchpad for extra storage, much like over-allocating an array to avoid resizing on append. If the stored data is smaller, those go unused, so if you pick the wrong amount, the overhead is too great. But if you hit the sweet spot, it has very significant perf benefits, not only because it avoids hitting the allocator on copies, but also because of data locality.
BTW, why wouldn't a lambda with a single usize field be common? I thought Rust captures everything by borrow by default; if so, doesn't the implementation simply store a frame pointer inside the lambda, and use it to access the captured variables? It seems like an obvious optimization...
Yes, I understand SSO. It’s just that these structures are already smaller than String/Vec would be by a third, so it’s harder to find something that fits.
> if so, doesn't the implementation simply store a frame pointer inside the lambda,
Yes. That’s what I was talking about. That’s why you’d only be able to store one usize inline. You’d be replacing that single pointer with data. String and Vec have double the available space!
(Incidentally, String can’t do SSO in Rust due to it exposing the underlying storage; there are SSO strings available in a package if it’s significant in your use-case.)
But if a lambda capture is already just a single pointer in this case, what exactly is on the heap when it's boxed? Like you said, it's one word for pointer to code, and one word for data. Why can't Box accommodate both directly within itself without heap-allocating? Is it the desire to have sizeof Box be a single word? But then why not offer SSO-enabled Box, or maybe even specifically FnBox, in a separate package, same as with strings?
Box<T> is always a single usize if T is Sized, and two usizes if T is not. T is not sized when it's a trait. If T is Sized, then Box<T> puts the T on the heap, and the Box itself is a pointer to it.
Box<Fn()> is a "trait object" the double pointer. It looks like this:
The first pointer is a pointer to the data, and the second pointer is a pointer to a vtable. So in the Box<Fn()> case, data is the captures, and the vtable is the code.
So when you write code like this:
// in a function body somewhere
let x = 5;
let f = Box::new(|| x);
Rust generates code that looks roughly like this:
// at item level
struct Env<'a> {
x: &'a i32,
}
// an impl of Fn for Env, i'm not writing that out
// in a function body somewhere
let x = 5;
let env = Env { x: &x };
let memory = GlobalAlloc::alloc(..);
// copy env into memory, i'm not writing that out
let f = TraitObject {
data: memory,
vtable: pointer_to_vtable_im_not_writing_out,
}
make sense? The Env is on the heap.
Before I move on, It's worth noting that, in the case of a closure which has no captures:
let f = Box::new(|| 5);
you get:
// at item level
struct Env;
// an impl of Fn for Env, i'm not writing that out
// in a function body somewhere
let x = 5;
let env = Env;
let memory = GlobalAlloc::alloc(..);
// copy env into memory, i'm not writing that out
let f = TraitObject {
data: memory,
vtable: pointer_to_vtable_im_not_writing_out,
}
since Env is a unit struct, it has zero size, and so gets optimized out at compile time, which also ends up removing all of the data stuff, which means it's back to a regular function pointer (fn instead of Fn).
Anyway.
So, if we were to do an SSO-like optimization here, we only have a single usize, the data pointer, to work with. We still need the function pointer, so we can't re-purpose it.
In theory, that would mean that an environment that has a total size of less than usize could be stored inline. It's not clear to me how often this is true, and if it would be worth it. But none of these internal representations are stable, so it's possible for Box<Fn()> at least.
Compare this to std::string. Different compilers implement it differently, but let's look at gcc:
You've got a pointer to the data, the size, and a union of the buffer vs the capacity. In the end, on a 64 bit system, this is 32 total bytes of space! Box<Fn()> by contrast, is 16 bytes total, and we can only use 8 bytes of that. Additionally, strings often do have individual byte data, but closures, given that they capture by default, have a size of at least 8. maybe a move closure that has a bunch of small numbers in it might make a good fit for some sort of SSO-style optimization here, but environments tend to be bigger and space is smaller than strings.
Not quite - that still doesn't explain why there can't be an SSO-optimized FnBox with extra padding that's there specifically to fit the kind of Fn that only needs to store the frame pointer, inline on the stack.
In fact, now I'm even more confused as to why it can't be done generically for Box<Fn>:
> The first pointer is a pointer to the data, and the second pointer is a pointer to a vtable. So in the Box<Fn()> case, data is the captures, and the vtable is the code.
If a given lambda can capture via a single frame pointer (because it borrows everything), why can't that frame pointer just be stored directly in the `data` field? Why does it have to indirected, with data pointing to another pointer on the heap?
And if borrow-capturing lambdas don't actually capture via frame pointer, why not?
Or are you saying that lambdas that borrow everything aren't actually all that common? But if they aren't, then why does capture by borrowing reference the default for lambdas?
> If a given lambda can capture via a single frame pointer (because it borrows everything), why can't that frame pointer just be stored directly in the `data` field?
If there's a single thing it's borrowing, then yes, it could. If there's any more than one, it won't fit.
> Or are you saying that lambdas that borrow everything aren't actually all that common?
I'm saying that closures that borrow exactly one thing aren't actually all that common.
I think you're misunderstanding what I mean by "frame pointer".
What I'm saying is that if a lambda is capturing local variables from a single stack frame by borrow (which ensures that it can't outlive them), then it doesn't need individual pointers to every variable. It just needs a pointer to the stack frame where they live, and it can access the individual variables by offset, same as the function to which that frame belongs does. It's compiler magic, of course - i.e. it means that such lambdas don't have a straightforward translation to a regular Rust object. But it's magic that behaves as if you had individual references, so it's a completely transparent optimization except for size of the resulting object.
On Intel architectures, you can think of it as stashing away EBP/RBP.
And lambdas that only capture locals from one frame, and all of them by reference, seems like a very common kind of lambda to me, making that optimization worthwhile.
Ah! Yes, I see now. I think that D implements closures this way? I thought you meant the closure’s conceptual stack frame.
As for commonality, the most common closures I see are:
* closures which have no environment
* closures that take the environment by move
* everything else
It’d be interesting to analyze crates.io and see though...and how much this would actually save you. I can't think of a time when the closure is only pointing to its parent's stack frame and you would box it. Box<Fn()> is mostly used for returning closures, and there, you'd be using a move closure to take the env by owner.
Closures have known size at compile-time, so they can be stored anywhere at all, although their types can't be named yet, so I don't think they can be stored in static memory.
Rust decides at compile time how long the data stored in a closure must live. You can create situations where that's hard to define, and the compiler, properly, won't permit that. It's very clever.
(Rust tends to use closures heavily, in places other languages don't. So they need all the performance they can get.)
One thing that's always concerned me about Rust is that everyone mononorphizes everything (e.g. closures are always unboxed except in the rare cases where dynamic dispatch is necessary). Hopefully this is a baseless fear, but isn't this a recipe for executable bloat?
Yes, and there have been some cases of people hitting very large binaries and having to put effort into slimming them down.
In most of those cases it's due to either wanting to run in very constrained space or distribution size, and then the problem is due to some blanket impl for a bunch of types that can safely be removed though. There are a few cargo submodules that will do executable size analysis with regard to monomorphization to show the outliers.
There's not really a good solution for this. Having your code be fast by default in exchange for more space seems like the trivially correct choice to make when most people have hundreds of gigabytes of free hard drive space and binaries don't get above a few megas, while CPU speed has stagnated. If they want runtime type matching instead, they can still do it.
Very large binaries can be a performance problem too if their access patterns end up trashing the cache. Memory access is a common bottleneck on modern CPUs. It depends how big "big" is in this case, and how much of it actually gets executed repeatedly.
It can be! And arguably people have leaned too hard on the decisions made in the std as an example: in std, everything is generic so that it can be inlined well, because std APIs underlie everything. At the application layer, this is not obviously what you want.
However, in many cases, a well designed generic API will be able take a trait object in the place of `T`. That way, at the application layer, you can decide to pass trait objects around, reducing code size and - maybe more importantly to you - compile times. cargo does this for example in some places where the performance regression is insignificant but it saves noticeable compile time.
Sometimes libraries accidentally don't set things up so that you can pass either a concrete `T` or a dynamically dispatched trait object to their APIs; we're hoping to find a way of making it less likely for this to go wrong in the future.
Something I've been thinking about a lot recently: would there be scope for a compiler mode which used virtual dispatch for generics (as well as trait objects) so as to speed up compile times? (and then you could compile the same code monomorphised for production).
Hmm, interesting the Niko thinks that MIR optimisation passes and CraneLift are more likely to happen soon. I so dearly want faster Rust compile times!
Monomorphization is a feature of compiler not the language, in the context of systems programming binary size often isn't the foremost priority.
Perhaps Rust compiler could get feature flag for controlling optimization priorities as I suspect in webasm world one would more often prefer more reasonable network transfer sizes than the fastest running version that is possible.
So, if you're writing in Rust, why not box everything, most of the time? Pay the cost of dereferencing to make it easier to reason about closures? Save unboxed values for situations where they're either trivial to reason about or you're sure there's a performance problem? Is this regarded as bad form?
(I don't really know Rust, but I'm watching with interest. As my comment may suggest, I'm more familiar with C and Python.)
You can. I'm not sure how much it's done or isn't done, really. Pre-1.0 Rust even had mandatory boxed closures, and until fairly recently (1.26?) you still had to box them in more situations than you do today.
Unboxed closures aren't any harder to reason about than boxed closures, and any function that accepts an unboxed closure accepts a boxed closure, too, which is why library authors should almost always prefer accepting unboxed closures (as withoutboats said in another comment.)
I think the general philosophy of Rust is that programmers should think about the data ownership semantics of their programs. Rather than boxing everything to make it easier to reason about closures, one should strive to write programs that use closures in a way that is easy to reason about.
Because, contrary to what the OP is saying, writing normal Rust is actually easy and straightforward. So you don't have to "box everything" by default. You only need that when you do some asynchronous work via generic interfaces.
... to get an initial implementation of. It's much easier to read, debug and refactor Rust code than in almost any other language that offers similar resource-efficiency.
Halfway-safe languages (including Haskell) that aren't Rust, have a nasty habit of eating memory (and usually CPU time, too) for breakfast, compared to equivalent programs in C, C++ and Rust. That's what I meant by "resource efficiency".
But writing a doubly linked list was already shown to be difficult [1], and now closures are too ... It really feels like this is not a language to "get things done". Please let someone prove me wrong.
+1. As a C++ developer with decade of experience, I'm finding Rust hard. It is a truly innovative language with a rising ecosystem that makes life of developers easier in a lot of areas. But overall the safety and performance benefits do not seem to be worth the effort if you just want to get things done. My thinking is, if you are smart enough to master Rust, and you do need tight control of memory that GC overhead is not worth it, you are probably smart enough to write safer C++.
> My thinking is, if you are smart enough to master Rust, and you do need tight control of memory that GC overhead is not worth it, you are probably smart enough to write safer C++.
Easy for you to say as a C++ developer! As someone who came to Rust as a JavaScript/PHP/Python developer, I greatly appreciate Rust checking all my work. I'm plenty smart enough to work out the problems that the compiler picks up (once I have an error message I can google for explanations and solutions), I just don't/didn't have the experience to know that my naive code was going to cause problems.
> if you are smart enough to master Rust, and you do need tight control of memory that GC overhead is not worth it, you are probably smart enough to write safer C++.
As both a C/C++ developer with more than a decade of experience, and a Rust developer, I'll posit that if you are smart enough to master Rust, you still aren't smart enough to write safer C++. Not even close. Rust might enlighten you in some ways, and avoid you doing some mistakes in C++, but without e.g. a borrow-checker, there are still too many ways to shoot yourself in the foot in C++, that Rust would find at compile time, while the equivalent C++ code would fail at runtime. If you're lucky and happen to hit the error conditions when you test it.
Yes, there's been lots of writing about this. I've been implementing linked lists in various ways over the last week (including right now), so this is very top of mind for me.
The core of it is two things: mindset, and how programmers think about learning languages.
Mindset: there's two things at play here. The first is that C programmers tend to reach for linked lists by default. It's a CS 101 data structure. Not super hard. A Rust programmer, however, would reach for a vector (or a deque) by default. For many use-cases, these structures are better, thanks to amortized allocations + cache reasons. As always, depends on exactly what you're doing. The second mindset issue is write vs use; C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list) Only if that fails do you write it yourself. As the ecosystem has filled out, this happens increasingly infrequently. So "a linked list is painful to write" just doesn't apply to the vast, vast majority of Rust programmers who are simply getting work done.
Learning: because linked lists are a CS 101 data structure, they're something people reach for when learning Rust. But different languages are different, and Rust is not C. Writing a good data structure isn't a beginner Rust topic, it's an intermediate to expert one. There's stuff Rust makes easy that C makes hard as well. You can't assume that topics are equally difficult across the languages. Even then, there's http://cglab.ca/~abeinges/blah/too-many-lists/book/.
TL;DR: linked lists being painful to implement is sorta true, but also not really relevant, other than people who try to learn Rust by building them and having a bad time. (Which is unfortunate, but many people don't as well, or have at least heard that they're hard and so have the right expectations going in.)
Now, I've gotta get back to my benchmarks: std::collections::LinkedList is twice as fast as my straightforward C linked list, and I gotta figure out where I messed up. I'll check back later for replies.
(If you're interested in this benchmark I'm working on, https://godbolt.org/z/lF1D85 is the disassembly. They look so close, I have no idea why 100,000 pushes, the Rust impl is taking 7.9038 ms on average, whereas the C impl is taking 15.413 ms. That seems very wrong...)
> C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list)
Not sure why you bring this up, since sooner/later people are going to need to implement their own data-structures(and this ownership problem will surface) and being it harder to implement is not relevant to package management(after all somebody did just implement that and made it available).
It's very relevant in the context of whether Rust is a 'get things done' language. Implementing a linked list is not a characteristic task of 'getting things done' in Rust, just like implementing a hash table isn't a characteristic task of 'getting things done' in Python. And when you do need to do it, implementing a data structure isn't any harder in unsafe Rust than in C++.
There's a theory of programming that says software development is fundamentally a process of devising and implementing data structures specifically tailored to the problem at hand.
This theory says well written software doesn't (and can't) simply stitch together various data structure implementations through generic interfaces. That in robust, elegant software there's no dividing line between where the fundamental data structure is implemented and where the application specific logic resides.
One classic example is the Thompson NFA. The argument is that the path to devising elegant solutions like the Thompson NFA is to think in terms of simple data structures tailored to particular problems. A toolbox of pre-implemented data structures is of little value because implementation matters and often needs to be tailored to the problem. It's not a matter of performance; it's that if your data structure implementations aren't tailored to the problem your use of them will require overly complex, opaquely layered code and you would (justifiably) architect your solution some other way; a way better suited to gluing together libraries but poorly suited to the actual functional problem.
I don't think this particular theory is right in any absolute sense. But I think it's more right in the domain that Rust targets, which means I believe the cost of implementing things like linked-lists and trees is underestimated; and that how often people will end up resorting to unsafe code (or recapitulating reliance on unchecked memory access, such reinventing pointers as indexes into arrays) is underestimated.
Most of my theoretical computer science knowledge was based on the fact that there are a bunch of basic well known algorithms and data structures and you build everything out of this.
Do you have resources on the approach "invent" such things on your own so they are better suited for the problem?
I have had to write specialized lookup tables multiple times for the problem at hand. In every case doing something custom gave non trivial speedups over existing off the shelf solutions.
I think the idea, as I understand it, comes from reading some of Rob Pike's works and people who think like him. For example,
Rule 5. Data dominates. If you've chosen the right data
structures and organized things well, the algorithms will
almost always be self-evident. Data structures, not
algorithms, are central to programming.
I read about the analysis of Thompson NFA, in the context a simplified version implemented by Rob Pike, in the chapter that Brian Kernighan wrote for "Beautiful Code: Leading Programmers Explain How They Think". Kernighan and Pike also wrote "The Practice of Programming", where the simplified version was originally published. Perhaps I'm making too much of that example, but it's what popped into my head.
Basically I think the idea is that if you farm all the complex data structure and algorithmic code to generic libraries, you're not apt to wrestle with the core functional problems. What functional features are you willing to sacrifice, if any, to create a more elegant solution? You can't begin to approach such a question unless you're also thinking, in very fundamental terms, about how to implement and combine the data structures and algorithms. There's an interplay between how you model a problem and how you implement it that effects every aspect of your design--or should effect every aspect of it. Using an off-the-shelf implementation brings a different cost-benefit profile, including wrt to composition. Sometimes it's better to use off-the-shell code, sometimes not; but you have to be prepared to think holistically about the problem.
A language that makes it more painful to implement or apply certain approaches internally effects your calculus from the outset.
A very simplified example: say you have some problem where a stack data structure (i.e. LIFO) is the obvious solution. If you think in terms of using off-the-shelf code, then in a language like Rust you're going to use something like a Vec or w'ever. But if your language supports recursion atop a dynamically growable stack, then a recursive solution will often be the simpler and more elegant approach. Both are, fundamentally, using stack data structures. But how you implement the stack can make a world of difference; conversely, which approach you choose is highly dependent on the problem and on other aspects of the larger implementation.
Taking that process to its logical end can result in a language like Go, where they've taken one of the primary problems in expressing highly-concurrent tasks, expressing a multitude of serial flows of execution that dynamically branch and collapse (not unlike the Thompson NFA), into the core language. A dynamic, growable call stack is fundamental to their approach.[1] Now step back and realize that Go itself is a solution to the specific problem of writing network services. It's obvious to most people how Go has sacrificed certain use cases for the benefit of others. It's an elegant solution for its problem domain because of how they were willing to apply and layer their abstractions. How you implement generic data structures matters. Among other things, you can combine abstract data structures more creatively and more powerfully when you're implementing them with a particular, shared goal mind.
Another good read along these line is, "Passing a Language through the Eye of a Needle: How the embeddability of Lua impacted its design". (https://queue.acm.org/detail.cfm?id=1983083) It discusses how the semantics of the Lua language were constrained by its problem domain, on the one hand; and how they were made more powerful by novel implementation solutions ...
You mean, creating your own data structures is the reason Go doesn't has genrics? Like, off-the-shelve solutions aren't optimized for the problem, so you have to write your own optized version anyway, so you don't need generics.
I think that's way too specific. Go lacks generics principally, AFAIU, because the designers had very specific notions about the complexity of the compiler and how that fit into the overall picture.
It true that there's an argument that says you often get more dividends for your effort wrestling with larger architecture and design than about, e.g., how easily you can write (or reuse) a binary tree implementation. A library won't help you implement the binary tree implementation for accessing a filesystem's on-disk data structures, for example. The value of some of the most beneficial use cases is often precluded to generic implementations. I think that reality played into why they discounted the value of generics, making them a low priority, but it's subtle and complex.
Generics (and meta programming more generally) cut both ways in terms of cost and benefit, at least when you think more holistically, and especially when you think about the complexity of the language and language implementation. It's a complex topic. There's no right answer, at least no right answer without a careful accounting of the context--the problems you're trying to solve and which aspects are the most critical or the most difficult to solve. That's the point.
Another way to think of it is that Go's structural typing (loosely speaking, duck typing) had much more bang-for-the-buck than generics, both abstractly and concretely. If you came to that conclusion early on, you may design and implement the language in a way that makes generics even more difficult to fit into the language. The original decision could have been perfectly legitimate, but over time it might seem like you simply didn't appreciate generics at all, especially when criticisms take the benefits of the existing design for granted without thinking about path dependency, etc.
FWIW, I've never written a single line of Go code.
Is it wrong to expect being able to implement standard data structures such as doubly-linked lists and trees with back-pointers having known complexity and performance trade-offs in a language advertising itself as replacement for a system programming language? After all, you should be able to implement standard libs in the language itself, and also to replace existing implementations.
It looks like they're different kinds of difficult. From your link:
« In hindsight and with a deeper understanding, it’s not surprising why a doubly linked list is so problematic. Each variable can only have 1 owner. If prev and next both hold pointers to a middle node, which is the owner? They can’t both be the owner. If one is the owner, another can borrow. But Rust won’t let you mutate while someone else is borrowing, so neither could actually modify the list! In general, if you have loops in your object graph you’re out of luck. »
So the solution for doubly linked lists is to write some "unsafe"-marked Rust once, really bang on it, and ship that in a crate full of generic data structures. This is acceptable to me; it's no worse than C.
With closures, it sounds like the issue is not that it's impossible, but that the lifetime and mutability analysis get tricky in some cases.
What's interesting is that the Rust community has turned this difficulty on its head: linked-lists are unnecessary, performance killers, and generally evil. (Ditto for trees.)
That's all true, if you squint really hard, gloss over the equivalencies, discount the additional complexity, and ignore the basic simplifying elegance of linked-lists (particularly the so-called intrusive data structure implementations). But it's dramatically overstated because of a certain defensiveness.
What is absolutely true is that cyclical referencing is the bane of static analysis, and anathema to a language that leans so heavily on its typing system for modeling language semantics. What you think that implies depends on your faith in how far type-based, lifetime-based static analysis can go toward addressing larger issues in the software ecosystem.
You hear fairly similar statements about linked lists from the C++ crowd too, where they're trivial to implement, so it's unlikely it's just defensive excuses.
They are are arguably about as trivial to implement in Rust. It becomes tricky when you add constraints: usually you want to avoid unsafe code, but even then you can just implement them on top of a vector and bypass any lifetime/aliasing issues.
> linked-lists are unnecessary, performance killers, and generally evil.
that's true on any CPU with more than 16kb of cache. linked lists were a good idea at the time of 486, not so much at the time of modern CPUs with 8+ megabytes of L3.
Closures are a fair thing to want to be easy, but I'm not sure "can't write basic data structures that someone has already written better than you will" isn't a feature.
Truth is that one of the reasons they're "hard" in rust is because it's actually harder than people think to make a proveably correct linked list (in the absence of a cycle-safe garbage collector). It's really just surfacing a cognitive dissonance common to the programming world.
(Note for clarity: closures are also hard to prove correct in the same environment, but there's a lot more need to write them in normal working code)
Additionally: Due to this, Rust will encourage you to gravitate towards pattern like immutable collections, or other 'functional-esque' coding styles. As a result, you usually end up writing code that's far more inherently reliable at runtime than something like a mutable doubly linked list. Just learning to code in 'idiomatic Rust' has made me a better coder overall, IMO, as has learning to write in pure functional languages.
I think most people definitely underestimate the amount of caution / design care required to implement even something as simple as a linked list with zero bugs, memory leaks, potential infinite loops in member functions, etc.
The Rust compiler prevents entire classes of bugs at compile time, and just requires that you to write an 'unsafe' block if you really want to go ahead with this sort of code without the compiler complaining. This emphasizes that you really do have to be careful and think through the logic and memory ownership semantics of the code you just wrote. People used to GC'ed languages will find this annoying to have to worry about at all, but that is inherently the price you must pay to eliminate GC pauses/overhead.
I'm not saying you should never use data structures that Rust makes hard to write, but that going into Rust thinking it's just going to be 're-skinned C++', or 'as easy as a GC language' is going to be a recipe for disappointment. If you allow yourself to learn a new way of thinking about low/systems-level coding, you may be pleasantly surprised. But if you're too "set in your ways" (whether it be of C/C++ or JS/Python/etc.), you're not going to see Rust's benefits.
Rust is a deeply different language than C/C++. I think people forget this, primarily because Rust is so powerful and efficient (with no inherent language overhead, allowing it to be used even in embedded environments and other systems programming tasks).
Writing a doubly linked list isn't that hard [1], and if you're willing to do it in unsafe rust, it's not any harder than any other language without a GC.
I think the name has done an excellent job of discouraging its use. Everyone in the community seems to agree that "contains unsafe code" is a big deal for a crate, and that taking that on when it isn't obviously necessary is sloppy.
This is the sort of really impressively shallow and baseless analysis that makes Hacker News so enjoyable to read.
These two blog posts have really nothing to do with one another, are describing unrelated problems with unrelated things, sharing only the fact that they both have to do with the Rust language and both describe something as difficult (but meaning pretty different things by the word) and you draw a conclusion that "Rust is not a language to 'get things done.'"
I don't know how to prove that Rust is "a language to 'get things done'" - this seems like an almost meaningless qualifier - but many people (including me) are getting things done using Rust every day.
I actually find that Rust is far more productive overall, when accounting for debugging time (or lack thereof) vs other languages!
It is precisely because Rust makes it difficult to implement a lot of bad ideas, that I find myself spending a tiny fraction of my time debugging Rust applications vs C/C++/others (including even high level GC languages).
I love that Rust encourages inherently reliable code, while also not stopping you from writing "unsafe" blocks in the (rare) cases where they're necessary. In fact, in every case so far where I thought 'maybe I should try an unsafe block', I started to realize that implementing this idea or data structure was actually riddled with hard memory management problems, or race conditions, etc. that Rust was preventing from even being possible at all.
P.S. Of course there's a steep learning curve to Rust at first, but it's not fair to count that against Rust -- unless you also weigh against C++ all the years it takes to really master it. IMO, Rust's learning curve is far less steep and painful than C++, it's just that many of us are biased and comfortable having already climbed the C++ learning cliff (so we tend to forget it is there, and how bad it is).
I did a basic test Rust program: load to strings certain files in a zip file. The first file in the archive happened to be UTF-16 instead of UFT-8 so a vanilla read_to_string for the file in the archive did not do the trick. I googled a bit and it seemed that, in order to be efficient, had to be done with unsafe code. Maybe I was very unlucky, but I was surprised that 5 minutes after trying rust for the very first time I had to use unsafe code.
I did not find a trivial way to go from the Vec<u8> returned by read_to_end to some kind of u16 container. Everything I found in Google involved unsafe code. Probably a function read_to_end returning a Vec<u16> would have been great.
Agh! Chunks is what I was looking for! I was trying to whip up an example[1] and was positive I had used a pair-wise iterator before. The best I came up w/ was zipping two iterators of the hi/lo bytes. -- I feel the parent's pain, because this is coming from someone who has been programming Rust since it had green threads and `~ / @` pointers.
I love Rustdoc, but I really wish it wasn't so obtuse when it came to casually browsing the various iterator traits. Perhaps Steve, for the benefit of myself and thread parent, you could point us to some better-edited literature for the various iterator methods?
P.S: just wanted to add, if I were faced w/ this issue in production code, I likely would've just reached for the excellent byteorder[2] crate. It's so useful for "bit twiddling" like this.
It is decidedly not a language to get things done. I say this as someone who put himself in the unfortunate position of challenging BurntSushi (author of ripgrep) to a coding duel, bragging that I could get LuaJIT to match his XSV performance (https://github.com/BurntSushi/xsv)
Now that it's done though, I see why people fall in love with Rust. It's really satisfying seeing Lumen's startup time drop from 200ms to 100ms.
But yes, like -- dude, at one point I just wanted to write a for loop like this, to grab some environment vars:
let mut lumen_host = "luajit";
let mut lua_path = "";
let mut node_path = "";
for (name, value) in env::vars() {
if name == "LUMEN_HOST" {
lumen_host = &value;
} else if name == "LUA_PATH" {
lua_path = &value;
} else if name == "NODE_PATH" {
node_path = &value;
}
}
println!("{} {} {} {}", bin, lumen_host, lua_path, node_path);
Good luck with that! I'm sure there's a way to coax Rust into please-allow-me-to-just-compile-this, but the borrow checker is a cruel taskmaster. Whatever the syntax is, that's not it, and spending literally an hour trying to figure out how to store an environment variable into a separate variable doesn't feel very productive.
That said, Cargo is amazing. It's truly a wonderful, delightful piece of software. Cargo crates plus a dynamic language seems like a recipe for success.
Is there a reason you looped through env::vars() rather than calling env::var on each key you wanted? That'd be much more straightforward:
let lumen_host = env::var("LUMEN_HOST").unwrap_or(String::from("luajit"));
let lua_path = env::var("LUA_PATH").unwrap_or(String::new());
let node_path = env::var("NODE_PATH").unwrap_or(String::new());
The reason it's difficult is that it simultaneously introduces the concepts of optionals, unwrapping, string processing, variable assignment, and lifetime management. It's not like it's impossible to figure out. I was only saying the workload was similar to "baby's first vi session".
I... am not sure. On one hand, it's instructive for language designers to know what turns out to be a barrier to entry. They're often unexpected things. And what's worse, users usually run into them and then quietly disappear; you almost never get the chance to see what trips newbies up in practice. It wasn't meant as a solid criticism, but more of a cathartic "yes, this language can be really counterintuitive at times." (Rust is in good company. It's the same reason Lisp is unpopular.)
On the other hand, you're absolutely right: the hypothesis is, given two equally-experienced programmers, one of them a Rust aficionado and the other a LuaJIT maniac, the LuaJIT dev will deliver reliable and maintainable software with an order of magnitude less effort. So you're right, that remains to be seen (to put it mildly).
Looking forward to seeing how close I can get to XSV's performance. It's a great benchmark.
You're welcome! I have had a lot more time to familiarize myself with the standard library than you probably have.
That being said.. A lot of this stuff is things that already exist that you don't need to write yourself. dirname, basename, join, even s is .to_string. It's also the same as str. getenv is env().unwrap_or().
Does `canonicalize` [1] not work in place of `realpath`?
You have a couple of helper functions, like `s` and `str` which you might consider using `to_str` and `to_string` in their place, as it's more idiomatic to use them directly rather than save characters.
And obviously you can replace `getenv` with `env::var`.
Just wanted to say thanks for taking the time to give feedback. Swinging through the jungles of a new ecosystem is always fun, and guideposts like this are quite helpful.
You don't think beginner's difficulty to use a language is worth criticizing considering a number of bike-shedding changes that are done to the language to make it easy for beginners?
I have no rust experience but this looks like this would crash in C++ or C at runtime. You're taking a reference to a string that will be deleted in the next iteration or when the loop completes. You have to make a copy of the strings if you want to keep the code as is.
>But writing a doubly linked list was already shown to be difficult [1], and now closures are too ...
That's a very shallow concern. Writing a "doubly linked list" is what you do in Rust with unsafe or will several other ways. It's also not something you usually do, you just use one of the several implementations in the library and third party libraries and get on with your actual program.
And this doesn't show closures to be that hard at all. It's the basic dynamic vs statically typed language thing, plus a couple of caveats to keep in mind. Hardly anything to write home about.
The fact the tons of people use Rust for production code already, and love it, doesn't give these concerns pause?
Surely the problems behind a doubly linked list apply to similar data structures (trees and graphs, notably - of which there are many more varieties than could be covered by a standard library). Writing a tree without resorting to unsafe seems like something which would be important.
In a DOM tree, any live node in the tree needs to keep the entire tree alive.
Which means you either need some sort of garbage collection setup, or reference counting (with cycle collection), or some sort of indirection where you really hold references to a "tree + node" pair and then have to worry about what happens when a node moves from one tree to another. Or something else, other than just having a bunch of objects that all point to each other without any explicit ownership semantics...
A team of three people including me have used Rust _daily_ for almost a year now for at Chain[1]. Rust is _by far_ much easier to use than C or C++ and lets us get things done with clear design, record-breaking performance[2] and utmost safety[3]. Basically, people who avoided C/C++ for years as unsafe, lacking usable abstractions and generally hard to use, switch to Rust and enjoy it.
It is trivial to implement doubly linked list. Just use unsafe.
What is difficult is to implement it in the safe Rust. But then try to proof that, say, C++, code doing the same is safe. It is very hard.
Besides, if one really wants cyclic structures in safe Rust, one can always do ancient Fortran trick and just represent pointers with array indexes. It may even be faster due to more cache-friendly memory layout.
Please consider listening to Bryan Cantrill's thoughts[1] on using Rust to, as you say, "get things done." -- In the presentation he explicitly calls out how learning Rust by trying to bang out a "trivial" data structure is very much the wrong approach. He posits that to understand the value(s) of Rust you must be willing to approach it from first principles. Let that sink in: a kernel & distributed systems programmer w/ decades of experience had to resist the urge to just bang out a linked list & instead opt to learn the language from first principles. That being said he seems to be quite[2] happy[3] with the language.
And for kicks, here's a quote from that Youtube video you link:
"So that was a surprise. (...) I've done zero profiling on this. I've made absolutely zero attempt to make this thing faster. None. In fact, you can pretty reasonably argue that I've gone out of my way to make it slower. And we are 40% faster than my C."
Which doesn't mean that rust is faster than C, but that changing your approach can, in fact, lead to results you wouldn't have expected.
Well, mileage varies there. For the most common for loops (equivalent to map or filter), I find it easy to see what they do at a glance. For many collection apis I have to look it up.
As someone who has recently started learning rust i can safely say closure issues where the hardest and most confusing things to learn how to fight with the borrow checker. This is especially the case since futures are becoming popular and require closures to be useful (obviously.)
This post covers a lot of the things I had to recently learn the "hard" way. Thanks!
157 comments
[ 1.9 ms ] story [ 209 ms ] threadTo be fair, typeof is not as useful without statement expressions (`({ ... })`), and statement expressions aren't as widely supported.
[1] All the major compilers support it (clang, GCC, IBM, Intel, Microsoft, Solaris, etc), plus or minus underscores in the identifier.
Every closure is an anonymous class in C++.
The runtime’s public API is very small: https://github.com/mackyle/blocksruntime/blob/master/BlocksR...
Behind the scenes it implements reference counting though.
Isn't it possible to avoid the whole slippery slope by capturing objects by value?
Your comment makes no sense. OP stated that your hypothetical problem isn't even a problem if the developer knows what he is doing, and your take from that is that there are more problems?
Actually, there is. C might be a colossal footgun but reasonably experienced developers do manage to avoid those problems.
Plus..... even if you could do that, WHY? C is a simple language, close to the "metal". If you want a language that has every-feature-and-their-mother, and can be close to the metal when needed, and can be used to blow both your feet off, just use C++.
Adding functional closures to C is somewhat akin to adding "asm" and "volatile" in Haskell.... even if you could do it, why would you? It just breaks the very essence of the language.
As others have already pointed out, C does not have references. It does however have pointers, and pointers are already copied by value.
> Then you’re looking at a deep copy
There is no such thing in standard C. Objects are copied by value, including pointers, and if you want to "deep copy" your custom data structures then you need to implement your custom cloning routines. However, naturally your custom cloning functions wouldn't be used directly to capture any variable.
> which can be expensive and/or very application-specific.
That's hardly specific to C.
> It’s hard to do copy by value generically.
Actually, it isn't. In fact with C it's quite trivial, and perhaps as trivial as it gets. There's no garbage collection thingy, no RAII, no deep copies, no refcounting... nothing. Just plain memcpy() from one object to another. That's it.
If you think being specific about what you want copied, freeing only when you know it's appropriate, and tracking any metadata around that yourself if a problem, don't work in C.
Get it right or risk a memory leak is the name of the game.
No, it's the C programming language. It has been like that since the 70s, and lots of people have been using it to develop high availability software for decades.
Just because some people never learned its basics nor are familiar with the subject that doesn't mean they have a point.
> The suggestion was that copy-everything-by-value solves the closure/memory issue with respect to copies.
No, that's quite wrong. The suggestion was thay passing objects by value would enable capturing variables without any of the slippery slope nonsense that was pointed out.
> This is also why C doesn’t have closures.
No, that's quite wrong as well. C doesn't have closures because no one bothered to add them, which is the exact same reason why C doesn't have namespaces or generics or any other feature ever. That's it.
https://en.cppreference.com/w/c/language/generic
https://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html
BTW, why wouldn't a lambda with a single usize field be common? I thought Rust captures everything by borrow by default; if so, doesn't the implementation simply store a frame pointer inside the lambda, and use it to access the captured variables? It seems like an obvious optimization...
> if so, doesn't the implementation simply store a frame pointer inside the lambda,
Yes. That’s what I was talking about. That’s why you’d only be able to store one usize inline. You’d be replacing that single pointer with data. String and Vec have double the available space!
(Incidentally, String can’t do SSO in Rust due to it exposing the underlying storage; there are SSO strings available in a package if it’s significant in your use-case.)
Box<T> is always a single usize if T is Sized, and two usizes if T is not. T is not sized when it's a trait. If T is Sized, then Box<T> puts the T on the heap, and the Box itself is a pointer to it.
Box<Fn()> is a "trait object" the double pointer. It looks like this:
The first pointer is a pointer to the data, and the second pointer is a pointer to a vtable. So in the Box<Fn()> case, data is the captures, and the vtable is the code.So when you write code like this:
Rust generates code that looks roughly like this: make sense? The Env is on the heap.Before I move on, It's worth noting that, in the case of a closure which has no captures:
you get: since Env is a unit struct, it has zero size, and so gets optimized out at compile time, which also ends up removing all of the data stuff, which means it's back to a regular function pointer (fn instead of Fn).Anyway.
So, if we were to do an SSO-like optimization here, we only have a single usize, the data pointer, to work with. We still need the function pointer, so we can't re-purpose it.
In theory, that would mean that an environment that has a total size of less than usize could be stored inline. It's not clear to me how often this is true, and if it would be worth it. But none of these internal representations are stable, so it's possible for Box<Fn()> at least.
Compare this to std::string. Different compilers implement it differently, but let's look at gcc:
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-...
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-...
You've got a pointer to the data, the size, and a union of the buffer vs the capacity. In the end, on a 64 bit system, this is 32 total bytes of space! Box<Fn()> by contrast, is 16 bytes total, and we can only use 8 bytes of that. Additionally, strings often do have individual byte data, but closures, given that they capture by default, have a size of at least 8. maybe a move closure that has a bunch of small numbers in it might make a good fit for some sort of SSO-style optimization here, but environments tend to be bigger and space is smaller than strings.
Does that all make sense?
In fact, now I'm even more confused as to why it can't be done generically for Box<Fn>:
> The first pointer is a pointer to the data, and the second pointer is a pointer to a vtable. So in the Box<Fn()> case, data is the captures, and the vtable is the code.
If a given lambda can capture via a single frame pointer (because it borrows everything), why can't that frame pointer just be stored directly in the `data` field? Why does it have to indirected, with data pointing to another pointer on the heap?
And if borrow-capturing lambdas don't actually capture via frame pointer, why not?
Or are you saying that lambdas that borrow everything aren't actually all that common? But if they aren't, then why does capture by borrowing reference the default for lambdas?
There can, you'd have to write it yourself.
> If a given lambda can capture via a single frame pointer (because it borrows everything), why can't that frame pointer just be stored directly in the `data` field?
If there's a single thing it's borrowing, then yes, it could. If there's any more than one, it won't fit.
> Or are you saying that lambdas that borrow everything aren't actually all that common?
I'm saying that closures that borrow exactly one thing aren't actually all that common.
What I'm saying is that if a lambda is capturing local variables from a single stack frame by borrow (which ensures that it can't outlive them), then it doesn't need individual pointers to every variable. It just needs a pointer to the stack frame where they live, and it can access the individual variables by offset, same as the function to which that frame belongs does. It's compiler magic, of course - i.e. it means that such lambdas don't have a straightforward translation to a regular Rust object. But it's magic that behaves as if you had individual references, so it's a completely transparent optimization except for size of the resulting object.
On Intel architectures, you can think of it as stashing away EBP/RBP.
And lambdas that only capture locals from one frame, and all of them by reference, seems like a very common kind of lambda to me, making that optimization worthwhile.
As for commonality, the most common closures I see are:
* closures which have no environment
* closures that take the environment by move
* everything else
It’d be interesting to analyze crates.io and see though...and how much this would actually save you. I can't think of a time when the closure is only pointing to its parent's stack frame and you would box it. Box<Fn()> is mostly used for returning closures, and there, you'd be using a move closure to take the env by owner.
And even if you do unnecessarily box: https://play.rust-lang.org/?gist=c16ac5983579d52d4997b3f4425...
If you click "show assembly", do_closure_stuff is compiled to:
It gets entirely optimized away anyway.(Rust tends to use closures heavily, in places other languages don't. So they need all the performance they can get.)
In most of those cases it's due to either wanting to run in very constrained space or distribution size, and then the problem is due to some blanket impl for a bunch of types that can safely be removed though. There are a few cargo submodules that will do executable size analysis with regard to monomorphization to show the outliers.
There's not really a good solution for this. Having your code be fast by default in exchange for more space seems like the trivially correct choice to make when most people have hundreds of gigabytes of free hard drive space and binaries don't get above a few megas, while CPU speed has stagnated. If they want runtime type matching instead, they can still do it.
However, in many cases, a well designed generic API will be able take a trait object in the place of `T`. That way, at the application layer, you can decide to pass trait objects around, reducing code size and - maybe more importantly to you - compile times. cargo does this for example in some places where the performance regression is insignificant but it saves noticeable compile time.
Sometimes libraries accidentally don't set things up so that you can pass either a concrete `T` or a dynamically dispatched trait object to their APIs; we're hoping to find a way of making it less likely for this to go wrong in the future.
Its also fairly common to have code like:
That could be instead monomorphised to be saving the inlining of _do_it's code bloat/generation penalty.Perhaps Rust compiler could get feature flag for controlling optimization priorities as I suspect in webasm world one would more often prefer more reasonable network transfer sizes than the fastest running version that is possible.
(I don't really know Rust, but I'm watching with interest. As my comment may suggest, I'm more familiar with C and Python.)
It's hard to write safe code. C is easier because you don't have to prove it's safe.
But writing a doubly linked list was already shown to be difficult [1], and now closures are too ... It really feels like this is not a language to "get things done". Please let someone prove me wrong.
[1] https://rcoh.me/posts/rust-linked-list-basically-impossible/
Lots of other problems are.
Easy for you to say as a C++ developer! As someone who came to Rust as a JavaScript/PHP/Python developer, I greatly appreciate Rust checking all my work. I'm plenty smart enough to work out the problems that the compiler picks up (once I have an error message I can google for explanations and solutions), I just don't/didn't have the experience to know that my naive code was going to cause problems.
As both a C/C++ developer with more than a decade of experience, and a Rust developer, I'll posit that if you are smart enough to master Rust, you still aren't smart enough to write safer C++. Not even close. Rust might enlighten you in some ways, and avoid you doing some mistakes in C++, but without e.g. a borrow-checker, there are still too many ways to shoot yourself in the foot in C++, that Rust would find at compile time, while the equivalent C++ code would fail at runtime. If you're lucky and happen to hit the error conditions when you test it.
The core of it is two things: mindset, and how programmers think about learning languages.
Mindset: there's two things at play here. The first is that C programmers tend to reach for linked lists by default. It's a CS 101 data structure. Not super hard. A Rust programmer, however, would reach for a vector (or a deque) by default. For many use-cases, these structures are better, thanks to amortized allocations + cache reasons. As always, depends on exactly what you're doing. The second mindset issue is write vs use; C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list) Only if that fails do you write it yourself. As the ecosystem has filled out, this happens increasingly infrequently. So "a linked list is painful to write" just doesn't apply to the vast, vast majority of Rust programmers who are simply getting work done.
Learning: because linked lists are a CS 101 data structure, they're something people reach for when learning Rust. But different languages are different, and Rust is not C. Writing a good data structure isn't a beginner Rust topic, it's an intermediate to expert one. There's stuff Rust makes easy that C makes hard as well. You can't assume that topics are equally difficult across the languages. Even then, there's http://cglab.ca/~abeinges/blah/too-many-lists/book/.
TL;DR: linked lists being painful to implement is sorta true, but also not really relevant, other than people who try to learn Rust by building them and having a bad time. (Which is unfortunate, but many people don't as well, or have at least heard that they're hard and so have the right expectations going in.)
Now, I've gotta get back to my benchmarks: std::collections::LinkedList is twice as fast as my straightforward C linked list, and I gotta figure out where I messed up. I'll check back later for replies.
(If you're interested in this benchmark I'm working on, https://godbolt.org/z/lF1D85 is the disassembly. They look so close, I have no idea why 100,000 pushes, the Rust impl is taking 7.9038 ms on average, whereas the C impl is taking 15.413 ms. That seems very wrong...)
Not sure why you bring this up, since sooner/later people are going to need to implement their own data-structures(and this ownership problem will surface) and being it harder to implement is not relevant to package management(after all somebody did just implement that and made it available).
This theory says well written software doesn't (and can't) simply stitch together various data structure implementations through generic interfaces. That in robust, elegant software there's no dividing line between where the fundamental data structure is implemented and where the application specific logic resides.
One classic example is the Thompson NFA. The argument is that the path to devising elegant solutions like the Thompson NFA is to think in terms of simple data structures tailored to particular problems. A toolbox of pre-implemented data structures is of little value because implementation matters and often needs to be tailored to the problem. It's not a matter of performance; it's that if your data structure implementations aren't tailored to the problem your use of them will require overly complex, opaquely layered code and you would (justifiably) architect your solution some other way; a way better suited to gluing together libraries but poorly suited to the actual functional problem.
I don't think this particular theory is right in any absolute sense. But I think it's more right in the domain that Rust targets, which means I believe the cost of implementing things like linked-lists and trees is underestimated; and that how often people will end up resorting to unsafe code (or recapitulating reliance on unchecked memory access, such reinventing pointers as indexes into arrays) is underestimated.
Most of my theoretical computer science knowledge was based on the fact that there are a bunch of basic well known algorithms and data structures and you build everything out of this.
Do you have resources on the approach "invent" such things on your own so they are better suited for the problem?
Would be nice if there was some theory around this I could follow :)
I read about the analysis of Thompson NFA, in the context a simplified version implemented by Rob Pike, in the chapter that Brian Kernighan wrote for "Beautiful Code: Leading Programmers Explain How They Think". Kernighan and Pike also wrote "The Practice of Programming", where the simplified version was originally published. Perhaps I'm making too much of that example, but it's what popped into my head.
Basically I think the idea is that if you farm all the complex data structure and algorithmic code to generic libraries, you're not apt to wrestle with the core functional problems. What functional features are you willing to sacrifice, if any, to create a more elegant solution? You can't begin to approach such a question unless you're also thinking, in very fundamental terms, about how to implement and combine the data structures and algorithms. There's an interplay between how you model a problem and how you implement it that effects every aspect of your design--or should effect every aspect of it. Using an off-the-shelf implementation brings a different cost-benefit profile, including wrt to composition. Sometimes it's better to use off-the-shell code, sometimes not; but you have to be prepared to think holistically about the problem.
A language that makes it more painful to implement or apply certain approaches internally effects your calculus from the outset.
A very simplified example: say you have some problem where a stack data structure (i.e. LIFO) is the obvious solution. If you think in terms of using off-the-shelf code, then in a language like Rust you're going to use something like a Vec or w'ever. But if your language supports recursion atop a dynamically growable stack, then a recursive solution will often be the simpler and more elegant approach. Both are, fundamentally, using stack data structures. But how you implement the stack can make a world of difference; conversely, which approach you choose is highly dependent on the problem and on other aspects of the larger implementation.
Taking that process to its logical end can result in a language like Go, where they've taken one of the primary problems in expressing highly-concurrent tasks, expressing a multitude of serial flows of execution that dynamically branch and collapse (not unlike the Thompson NFA), into the core language. A dynamic, growable call stack is fundamental to their approach.[1] Now step back and realize that Go itself is a solution to the specific problem of writing network services. It's obvious to most people how Go has sacrificed certain use cases for the benefit of others. It's an elegant solution for its problem domain because of how they were willing to apply and layer their abstractions. How you implement generic data structures matters. Among other things, you can combine abstract data structures more creatively and more powerfully when you're implementing them with a particular, shared goal mind.
Another good read along these line is, "Passing a Language through the Eye of a Needle: How the embeddability of Lua impacted its design". (https://queue.acm.org/detail.cfm?id=1983083) It discusses how the semantics of the Lua language were constrained by its problem domain, on the one hand; and how they were made more powerful by novel implementation solutions ...
It true that there's an argument that says you often get more dividends for your effort wrestling with larger architecture and design than about, e.g., how easily you can write (or reuse) a binary tree implementation. A library won't help you implement the binary tree implementation for accessing a filesystem's on-disk data structures, for example. The value of some of the most beneficial use cases is often precluded to generic implementations. I think that reality played into why they discounted the value of generics, making them a low priority, but it's subtle and complex.
Generics (and meta programming more generally) cut both ways in terms of cost and benefit, at least when you think more holistically, and especially when you think about the complexity of the language and language implementation. It's a complex topic. There's no right answer, at least no right answer without a careful accounting of the context--the problems you're trying to solve and which aspects are the most critical or the most difficult to solve. That's the point.
Another way to think of it is that Go's structural typing (loosely speaking, duck typing) had much more bang-for-the-buck than generics, both abstractly and concretely. If you came to that conclusion early on, you may design and implement the language in a way that makes generics even more difficult to fit into the language. The original decision could have been perfectly legitimate, but over time it might seem like you simply didn't appreciate generics at all, especially when criticisms take the benefits of the existing design for granted without thinking about path dependency, etc.
FWIW, I've never written a single line of Go code.
« In hindsight and with a deeper understanding, it’s not surprising why a doubly linked list is so problematic. Each variable can only have 1 owner. If prev and next both hold pointers to a middle node, which is the owner? They can’t both be the owner. If one is the owner, another can borrow. But Rust won’t let you mutate while someone else is borrowing, so neither could actually modify the list! In general, if you have loops in your object graph you’re out of luck. »
So the solution for doubly linked lists is to write some "unsafe"-marked Rust once, really bang on it, and ship that in a crate full of generic data structures. This is acceptable to me; it's no worse than C.
With closures, it sounds like the issue is not that it's impossible, but that the lifetime and mutability analysis get tricky in some cases.
That's all true, if you squint really hard, gloss over the equivalencies, discount the additional complexity, and ignore the basic simplifying elegance of linked-lists (particularly the so-called intrusive data structure implementations). But it's dramatically overstated because of a certain defensiveness.
What is absolutely true is that cyclical referencing is the bane of static analysis, and anathema to a language that leans so heavily on its typing system for modeling language semantics. What you think that implies depends on your faith in how far type-based, lifetime-based static analysis can go toward addressing larger issues in the software ecosystem.
that's true on any CPU with more than 16kb of cache. linked lists were a good idea at the time of 486, not so much at the time of modern CPUs with 8+ megabytes of L3.
See https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vecto...
Truth is that one of the reasons they're "hard" in rust is because it's actually harder than people think to make a proveably correct linked list (in the absence of a cycle-safe garbage collector). It's really just surfacing a cognitive dissonance common to the programming world.
(Note for clarity: closures are also hard to prove correct in the same environment, but there's a lot more need to write them in normal working code)
I think most people definitely underestimate the amount of caution / design care required to implement even something as simple as a linked list with zero bugs, memory leaks, potential infinite loops in member functions, etc.
The Rust compiler prevents entire classes of bugs at compile time, and just requires that you to write an 'unsafe' block if you really want to go ahead with this sort of code without the compiler complaining. This emphasizes that you really do have to be careful and think through the logic and memory ownership semantics of the code you just wrote. People used to GC'ed languages will find this annoying to have to worry about at all, but that is inherently the price you must pay to eliminate GC pauses/overhead.
I'm not saying you should never use data structures that Rust makes hard to write, but that going into Rust thinking it's just going to be 're-skinned C++', or 'as easy as a GC language' is going to be a recipe for disappointment. If you allow yourself to learn a new way of thinking about low/systems-level coding, you may be pleasantly surprised. But if you're too "set in your ways" (whether it be of C/C++ or JS/Python/etc.), you're not going to see Rust's benefits.
Rust is a deeply different language than C/C++. I think people forget this, primarily because Rust is so powerful and efficient (with no inherent language overhead, allowing it to be used even in embedded environments and other systems programming tasks).
[1]: https://www.reddit.com/r/programming/comments/7zbi6s/why_wri...
These two blog posts have really nothing to do with one another, are describing unrelated problems with unrelated things, sharing only the fact that they both have to do with the Rust language and both describe something as difficult (but meaning pretty different things by the word) and you draw a conclusion that "Rust is not a language to 'get things done.'"
I don't know how to prove that Rust is "a language to 'get things done'" - this seems like an almost meaningless qualifier - but many people (including me) are getting things done using Rust every day.
It is precisely because Rust makes it difficult to implement a lot of bad ideas, that I find myself spending a tiny fraction of my time debugging Rust applications vs C/C++/others (including even high level GC languages).
I love that Rust encourages inherently reliable code, while also not stopping you from writing "unsafe" blocks in the (rare) cases where they're necessary. In fact, in every case so far where I thought 'maybe I should try an unsafe block', I started to realize that implementing this idea or data structure was actually riddled with hard memory management problems, or race conditions, etc. that Rust was preventing from even being possible at all.
P.S. Of course there's a steep learning curve to Rust at first, but it's not fair to count that against Rust -- unless you also weigh against C++ all the years it takes to really master it. IMO, Rust's learning curve is far less steep and painful than C++, it's just that many of us are biased and comfortable having already climbed the C++ learning cliff (so we tend to forget it is there, and how bad it is).
I'm sure there's a package that makes this easy, but this took me about ten minutes to toss together from scratch.
I love Rustdoc, but I really wish it wasn't so obtuse when it came to casually browsing the various iterator traits. Perhaps Steve, for the benefit of myself and thread parent, you could point us to some better-edited literature for the various iterator methods?
P.S: just wanted to add, if I were faced w/ this issue in production code, I likely would've just reached for the excellent byteorder[2] crate. It's so useful for "bit twiddling" like this.
[1]: https://play.rust-lang.org/?gist=4b4ff7263d9744caeb8bacd4c0d...
[2]: https://docs.rs/byteorder/1.2.6/byteorder/trait.ReadBytesExt...
> Perhaps Steve, for the benefit of myself and thread parent, you could point us to some better-edited literature for the various iterator methods?
I used that page to find this. I knew it was "chunks" or "windows" or something, so I just looked at them (I guessed windows, but I was wrong).
It took hours to figure out how to implement this in rust: https://github.com/sctb/lumen/blob/master/bin/lumen
If you want to see an "expert" programmer's attempt at making sense of the language, here you go: https://gist.github.com/shawwn/4d7a89188cac72f3e591f47c84d3c...
Now that it's done though, I see why people fall in love with Rust. It's really satisfying seeing Lumen's startup time drop from 200ms to 100ms.
But yes, like -- dude, at one point I just wanted to write a for loop like this, to grab some environment vars:
Good luck with that! I'm sure there's a way to coax Rust into please-allow-me-to-just-compile-this, but the borrow checker is a cruel taskmaster. Whatever the syntax is, that's not it, and spending literally an hour trying to figure out how to store an environment variable into a separate variable doesn't feel very productive.That said, Cargo is amazing. It's truly a wonderful, delightful piece of software. Cargo crates plus a dynamic language seems like a recipe for success.
Out of curiosity, did you spot any other antipatterns? I'm sure there are a bunch: https://gist.github.com/shawwn/4d7a89188cac72f3e591f47c84d3c...
I poo poo the language a lot, but it's satisfying to get the hang of it.
Curious about that block in particular. I have no idea what I'm doing, so it'd be somewhat shocking if that were idiomatic.The question is why. The relevant examples are everywhere:
https://doc.rust-lang.org/std/env/fn.var.html
https://doc.rust-lang.org/std/env/fn.vars.html
https://doc.rust-lang.org/book/second-edition/ch12-05-workin...
http://siciarz.net/24-days-rust-environment-variables/
The reason it's difficult is that it simultaneously introduces the concepts of optionals, unwrapping, string processing, variable assignment, and lifetime management. It's not like it's impossible to figure out. I was only saying the workload was similar to "baby's first vi session".
That would be like criticizing vi based on "baby's first vi session", because "couldn't even exit the editor!".
On the other hand, you're absolutely right: the hypothesis is, given two equally-experienced programmers, one of them a Rust aficionado and the other a LuaJIT maniac, the LuaJIT dev will deliver reliable and maintainable software with an order of magnitude less effort. So you're right, that remains to be seen (to put it mildly).
Looking forward to seeing how close I can get to XSV's performance. It's a great benchmark.
That being said.. A lot of this stuff is things that already exist that you don't need to write yourself. dirname, basename, join, even s is .to_string. It's also the same as str. getenv is env().unwrap_or().
> Curious about that block in particular.
I would call https://doc.rust-lang.org/std/fs/fn.canonicalize.html and be done with it, instead of importing libc and going through all of this.
In the end, this should be like 40LOC, 50 tops, if you made use of the standard library rather than trying to re-implement it all :)
You have a couple of helper functions, like `s` and `str` which you might consider using `to_str` and `to_string` in their place, as it's more idiomatic to use them directly rather than save characters.
And obviously you can replace `getenv` with `env::var`.
1: https://doc.rust-lang.org/std/path/struct.Path.html#method.c...
Criticizing a language by how easy it is to write the "first 20 lines" doesn't sound really fare...
That's a very shallow concern. Writing a "doubly linked list" is what you do in Rust with unsafe or will several other ways. It's also not something you usually do, you just use one of the several implementations in the library and third party libraries and get on with your actual program.
And this doesn't show closures to be that hard at all. It's the basic dynamic vs statically typed language thing, plus a couple of caveats to keep in mind. Hardly anything to write home about.
The fact the tons of people use Rust for production code already, and love it, doesn't give these concerns pause?
https://github.com/servo/servo/blob/master/components/script...
https://manishearth.github.io/blog/2015/09/01/designing-a-gc...
Which means you either need some sort of garbage collection setup, or reference counting (with cycle collection), or some sort of indirection where you really hold references to a "tree + node" pair and then have to worry about what happens when a node moves from one tree to another. Or something else, other than just having a bunch of objects that all point to each other without any explicit ownership semantics...
[1] Bulletproofs crypto library: https://github.com/dalek-cryptography/bulletproofs/
[2] https://blog.chain.com/faster-bulletproofs-with-ristretto-av...
[3] https://blog.chain.com/bulletproof-multi-party-computation-i...
What is difficult is to implement it in the safe Rust. But then try to proof that, say, C++, code doing the same is safe. It is very hard.
Besides, if one really wants cyclic structures in safe Rust, one can always do ancient Fortran trick and just represent pointers with array indexes. It may even be faster due to more cache-friendly memory layout.
[1]: https://www.youtube.com/watch?v=aWbGPMxs0AM
[2]:https://twitter.com/bcantrill/status/1035335403186806784
[3]: https://twitter.com/bcantrill/status/1038495464692146176
"So that was a surprise. (...) I've done zero profiling on this. I've made absolutely zero attempt to make this thing faster. None. In fact, you can pretty reasonably argue that I've gone out of my way to make it slower. And we are 40% faster than my C."
Which doesn't mean that rust is faster than C, but that changing your approach can, in fact, lead to results you wouldn't have expected.
When you see filter, map, or max_by, you know what the code does right away.
This post covers a lot of the things I had to recently learn the "hard" way. Thanks!