Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Under the hood: Vec

marma.dev

Post reply on HN
Print view View original

131–140 of 142 posts

Re: Under the hood: Vec<T>

#131

Post by teo_zero »

pornel wrote: post #93
smallstepforman wrote: post #40

Earlier quoted context omitted.

From your description, I cannot determine the difference. Engineers like exact things, whats this fuzzy concept called “hint”?

reserve() reallocates by at least doubling the capacity. reserve_exact() reallocates by exactly what you ask for. If you reserve() space for 1 more element a 1000 times, you will get ~30 reallocations, not 1000. This inexact nature is useful when the total size is unknown, but you append in batches. You could implement your own amortised growth strategy, but having one built-in makes it simple for different functions…

> If you reserve() space for 1 more element a 1000 times, you will get ~30 reallocations, not 1000.

Surely you mean ~10 reallocations, because 2^10=1024, right?

Re: Under the hood: Vec<T>

#133

Post by James_K »

pornel wrote: post #15
James_K wrote: post #8

Earlier quoted context omitted.

Oh, I never knew that Rust had variance. I always just assumed everything was invariant. Strange that they've got no way to write it down in the type system.

In prehistoric Rust, variance used to be named more explicitly. However, the terminology of covariant and contravariant subtyping of lifetimes is a language theory jargon. This is the right perspective for language design, but programmers using the language don't necessarily use these terms. It's been replaced with a "by example" approach. It's much easier to teach it: just add a fake field that acts if you had this…

1 point by James_K 0 minutes ago | root | parent | next | edit | delete [–]

That's horrible design. I was utterly perplexed whenever the compiler asked me to add one of those strange fields to a struct. If it had just asked me to include the variance in generic parameters, I would have had no such confusion. Asking programmers to learn the meaning of an important concept in programming is entirely reasonable, especially in Rust which is a language for advanced programmers that expects knowledge of many other more complicated things.

What's more, the implicit variance approach might create dangerous code. It is possible to break the interface for a module without making any change to its type signature. The entire point of types is to provide a basic contract for the behaviour of an object. A type system with variance in it that doesn't let you write it down in the signature is deficient in this property.

Re: Under the hood: Vec<T>

#134

Post by James_K »

kannanvijayan wrote: post #63
branko_d wrote: post #33

Earlier quoted context omitted.

Why? It's just a property of type transformation. Assuming Parent - If Generic : it's covariant. - If Generic -> Generic : it's contravariant. - Otherwise: it's invariant. Or at least it's that straightforward in C#. Are there complications in Rust?

The difficulty is that even trivial generic types aren't cleanly one or the other. A mutable reference type is covariant on read, and contra on write. Scala was the first language in my exposure to try to simplify that away by lifting the variance annotations into the type parameter directly. It reduced some of the power but it made things easier to understand for developers. A full variance model would annotate spec…

> A mutable reference type is covariant on read, and contra on write.

No it isn't. The type is covariant because a reference is a subtype of all parent types. The the function read must have it's argument invariant because it both takes and returns an instance of the type. I think you're confusing the variance of types for the variance of instances of those types. Read is effectively a Function(t: type, Function(ref t, t)). If it was covariant as you suggest, we would have a serious problem. Consider that (read Child) works by making a memory read for the first (sizeof Child) bytes of it's argument. If read were covariant, then that would imply you could call (read Child) on a Parent type and get a Parent back, but that won't work because (sizeof Child) can be less than (sizeof Parent). Read simply appears covariant because it's generic. (read Child) ≠ (read Parent), but you can get (read Parent). It also appears contravariant because you can get (read Grandchild).

Scala doesn't simplify anything, that's just how variance works.

Re: Under the hood: Vec<T>

#135

Post by [deleted] »

James_K wrote: post #133
pornel wrote: post #15

Earlier quoted context omitted.

In prehistoric Rust, variance used to be named more explicitly. However, the terminology of covariant and contravariant subtyping of lifetimes is a language theory jargon. This is the right perspective for language design, but programmers using the language don't necessarily use these terms. It's been replaced with a "by example" approach. It's much easier to teach it: just add a fake field that acts if you had this…

1 point by James_K 0 minutes ago | root | parent | next | edit | delete [–] That's horrible design. I was utterly perplexed whenever the compiler asked me to add one of those strange fields to a struct. If it had just asked me to include the variance in generic parameters, I would have had no such confusion. Asking programmers to learn the meaning of an important concept in programming is entirely reasonable, especia…

[deleted]

Re: Under the hood: Vec<T>

#136

Post by James_K »

SonOfLilit wrote: post #10
James_K wrote: post #7

While safe Rust may be relatively simple to write, and certainly easier to write than safe C, this article has someone added to my belief that unsafe Rust is far too difficult to write. Perhaps some of this is deliberate, as a kind of defence mechanism against people using it willy-nilly, it still seems over-designed.

When I was young I peeked into the C++ stdlib, which is probably the best thing to compare this to. It was orders of magnitude worse.

Would you consider this to be indicative of the quality of the C++ language? I think the standard library should usually be an example of optimal code with respect to performance, and when it is very complicated this would indicate, to me, that the language makes good code complicated.

If you look at an advanced C library, you'll see perhaps some odd tricks or nifty algorithms, but you probably won't see something that leaves you scratching your head about what the code is even asking the computer to do.

Re: Under the hood: Vec<T>

#137

Post by kannanvijayan »

James_K wrote: post #134
kannanvijayan wrote: post #63

Earlier quoted context omitted.

The difficulty is that even trivial generic types aren't cleanly one or the other. A mutable reference type is covariant on read, and contra on write. Scala was the first language in my exposure to try to simplify that away by lifting the variance annotations into the type parameter directly. It reduced some of the power but it made things easier to understand for developers. A full variance model would annotate spec…

> A mutable reference type is covariant on read, and contra on write. No it isn't. The type is covariant because a reference is a subtype of all parent types. The the function read must have it's argument invariant because it both takes and returns an instance of the type. I think you're confusing the variance of types for the variance of instances of those types. Read is effectively a Function(t: type, Function(ref…

Even in your own description, it is clear that with regards to _correctness_, the variance model bifurcates between the read and the write method.

The discussion about the type sizes is a red herring. If the type system in question makes two types of differing sizes not able to be subtypes of each other, then calling these things "Child" and "Parent" is just a labeling confusion on types unrelated by a subtyping relationship. The discussion doesn't apply at all to that case.

The variance is a property of the algorithm with respect to the type. A piece of code that accepts a reference to some type A and only ever reads from it can correctly accept a reference to a subtype of A.

A piece of code that accepts a reference to a type A and only ever writes to it can correctly accept a reference to a supertype of A.

In an OO language, an instance method is covariant whenever the subject type occurs in return position (read analogue), and it's contravariant whenever the subject type occurs in a parameter position (write analogue). On instance methods where both are present, you naturally reduce to the intersection of those two sets, which causes them to be annotated as invariant.

Re: Under the hood: Vec<T>

#138

Post by tialaramex »

panzi wrote: post #102
tialaramex wrote: post #31

Because this is focused on how the data structure works it doesn't mention lots of nice API design choices in Rust. The one I particularly want to call out because it came up this morning is providing both Vec::reserve and Vec::reserve_exact Vec::reserve lets us hint about our upcoming capacity expectations without damaging the O(1) amortized growth which is the whole point of this collection type, but it can waste s…

Just today I saw a (2 year old) video on that very topic in Rust and C++: https://www.youtube.com/watch?v=algDLvbl1YY Towards the end they mention what to use instead in C++ to get the same characteristics as Rust's Vec::reserve: vec.insert( vec.cend(), std::move_iterator(newElems.begin()), std::move_iterator(newElems.end()) );

This is roughly analogous to Vec's specialised Extend implementation. Like that feature it only helps if you've got a similar API shape you're adapting. If we need to make newElems then we're probably not getting a perf win from this.

Re: Under the hood: Vec<T>

#139

Post by James_K »

kannanvijayan wrote: post #137
James_K wrote: post #134

Earlier quoted context omitted.

> A mutable reference type is covariant on read, and contra on write. No it isn't. The type is covariant because a reference is a subtype of all parent types. The the function read must have it's argument invariant because it both takes and returns an instance of the type. I think you're confusing the variance of types for the variance of instances of those types. Read is effectively a Function(t: type, Function(ref…

Even in your own description, it is clear that with regards to _correctness_, the variance model bifurcates between the read and the write method. The discussion about the type sizes is a red herring. If the type system in question makes two types of differing sizes not able to be subtypes of each other, then calling these things "Child" and "Parent" is just a labeling confusion on types unrelated by a subtyping rela…

> A piece of code that accepts a reference to some type A and only ever reads from it can correctly accept a reference to a subtype of A.

The same is true of a piece of code that writes through the reference or returns it. That's how sub-typing works.

> A piece of code that accepts a reference to a type A and only ever writes to it can correctly accept a reference to a supertype of A.

Have you ever programmed in a language with subtyping? Let me show you an example from Java (a popular object oriented programming language).

  class Parent {}
  class Child {
      int x;
  }
  
  class Example {
      static void writeToChild(Child c) {
         c.x = 20;
      }
      static void main() {
         writeToChild(new Parent());
      }
  }
This code snippet doesn't compile, but suppose the compiler allowed us to do so, do you think it could work? No. The function writeToChild cannot accept a reference to the supertype even though it only writes through the reference.

I've seen a lot of people in this comment section talking about read and write which I find really odd. They have nothing to do with variance. The contravariant property is a property of function values and their parameters. It is entirely unrelated to the body of the function. A language without higher order functions will actually never have a contravariant type within it. This is why many popular OOP languages do not have them.

Re: Under the hood: Vec<T>

#140

Post by kannanvijayan »

James_K wrote: post #139
kannanvijayan wrote: post #137

Earlier quoted context omitted.

Even in your own description, it is clear that with regards to _correctness_, the variance model bifurcates between the read and the write method. The discussion about the type sizes is a red herring. If the type system in question makes two types of differing sizes not able to be subtypes of each other, then calling these things "Child" and "Parent" is just a labeling confusion on types unrelated by a subtyping rela…

> A piece of code that accepts a reference to some type A and only ever reads from it can correctly accept a reference to a subtype of A. The same is true of a piece of code that writes through the reference or returns it. That's how sub-typing works. > A piece of code that accepts a reference to a type A and only ever writes to it can correctly accept a reference to a supertype of A. Have you ever programmed in a la…

> The same is true of a piece of code that writes through the reference or returns it. That's how sub-typing works.

But it is not true that it is correctly typed with respect to a a supertype of A (it is not valid to call the code with a reference to a supertype of A).

Code that only writes through the reference is correctly typed with respect to a super-type of A (it is valid to call the code with a reference to a supertype of A).

> Have you ever programmed in a language with subtyping?

Sigh, keep that snark for the twitter battles. I don't care enough about this to get snippy about it or to deal with folks who do.

Post reply on HN