3 ms·

I'm surprised that the reviewer was so ignorant of amortized constant time insertion.

by pitaj 3y ago

rossjudson 3y ago
I am not at all surprised. Kids these days have no idea what CPUs can do. ;) I periodically have interview candidates work through problems involving binary search, then switch to bounded and ask them how to make it go faster over N elements, where N is < 1e3. The answer is "just linear search, because CPUs really like to do that".
- beltsazar 3y ago
  But amortized analysis has nothing to do with what CPUs can do. CS students learn it in an algorithm course, not in a computer architecture course.
lifthrasiir 3y ago
If I'm being super pedantic, I would argue that while `string::push_back` should take amortized constant time, `string::append` has no such guarantee [1]. So it is technically possible for `my_string += "a";` (same to `string::append`) will reallocate every time. Very pedantic indeed, but I have seen some C++ implementation where `std::vector<T>` is an alias to `std::deque<T>`, so... One thing I don't like about lemire's phrasing is that he only looks at the current, often only most available, implementations and doesn't make this point explicit for most cases. EDIT: Thankfully he does acknowledge that in a later post [2]. [1] https://timsong-cpp.github.io/cppwp/n4861/strings#string.append https://timsong-cpp.github.io/cppwp/n4861/strings#string.app... [2] https://lemire.me/blog/2023/10/23/appending-to-an-stdstring-character-by-character-how-does-the-capacity-grow/ https://lemire.me/blog/2023/10/23/appending-to-an-stdstring-...
- spacechild1 3y ago
  > but I have seen some C++ implementation where `std::vector<T>` is an alias to `std::deque<T>`, so I have a hard time believing that because std::vector guarantees that the memory is contiguous.
  - lifthrasiir 3y ago
    Yeah, it wouldn't be standard-compliant, and I think it was very ancient one---at least as old as STLport I believe.
euiq 3y ago
This feels like a conversation where it would have been useful for the participants to be very explicit about the points they were trying to convey: the reviewer could have said "Isn't this a quadratic algorithm, because each call to `+=` reallocates `escaped_file_path`?" (or whatever their specific concern was; I may have misunderstood), and the author's initial response could have been "No, because the capacity of the string is doubled when necessary."

I'm surprised that the reviewer was so ignorant of amortized constant time insertion.

by pitaj 3y ago

I'm surprised that the reviewer was so ignorant of amortized constant time insertion.

I am not at all surprised. Kids these days have no idea what CPUs can do. ;) I periodically have interview candidates work through problems involving binary search, then switch to bounded and ask them how to make it go faster over N elements, where N is < 1e3. The answer is "just linear search, because CPUs really like to do that".

beltsazar 3y ago
But amortized analysis has nothing to do with what CPUs can do. CS students learn it in an algorithm course, not in a computer architecture course.

lifthrasiir 3y ago

If I'm being super pedantic, I would argue that while `string::push_back` should take amortized constant time, `string::append` has no such guarantee [1]. So it is technically possible for `my_string += "a";` (same to `string::append`) will reallocate every time. Very pedantic indeed, but I have seen some C++ implementation where `std::vector<T>` is an alias to `std::deque<T>`, so... One thing I don't like about lemire's phrasing is that he only looks at the current, often only most available, implementations and doesn't make this point explicit for most cases. EDIT: Thankfully he does acknowledge that in a later post [2]. [1] https://timsong-cpp.github.io/cppwp/n4861/strings#string.append https://timsong-cpp.github.io/cppwp/n4861/strings#string.app... [2] https://lemire.me/blog/2023/10/23/appending-to-an-stdstring-character-by-character-how-does-the-capacity-grow/ https://lemire.me/blog/2023/10/23/appending-to-an-stdstring-...

spacechild1 3y ago
> but I have seen some C++ implementation where `std::vector<T>` is an alias to `std::deque<T>`, so I have a hard time believing that because std::vector guarantees that the memory is contiguous.
- lifthrasiir 3y ago
  Yeah, it wouldn't be standard-compliant, and I think it was very ancient one---at least as old as STLport I believe.

euiq 3y ago

This feels like a conversation where it would have been useful for the participants to be very explicit about the points they were trying to convey: the reviewer could have said "Isn't this a quadratic algorithm, because each call to `+=` reallocates `escaped_file_path`?" (or whatever their specific concern was; I may have misunderstood), and the author's initial response could have been "No, because the capacity of the string is doubled when necessary."