4 ms·

Daniel’s PR to implement this in node.js[1] is case study in: - crafting a high context yet succinct description - addressing PR feedback well - giving respe

Daniel’s PR to implement this in node.js[1] is case study in: - crafting a high context yet succinct description - addressing PR feedback well - giving respect to a pedantic commenter who understands the inner workings far less than Daniel while not conceded to make a destructive change. I will share this PR widely as arole model in open source contributions. [1] https://github.com/nodejs/node/pull/50288 https://github.com/nodejs/node/pull/50288

pitaj 3y ago
I'm surprised that the reviewer was so ignorant of amortized constant time insertion.
- 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."
deleted 3y ago
[deleted]
rossjudson 3y ago
The same thing struck me as well. This is one of the best optimization professionals on the planet, showing up with a huge improvement, and receiving some misplaced arrogance. The lesson here is to always, always watch your own review tone, and not make this mistake. The other lesson is that when a PR shows up with this kind of technical information attached to it, spend the 60 seconds it takes to Google for "lemire".

pitaj 3y ago

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

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."

deleted 3y ago

[deleted]

rossjudson 3y ago

The same thing struck me as well. This is one of the best optimization professionals on the planet, showing up with a huge improvement, and receiving some misplaced arrogance. The lesson here is to always, always watch your own review tone, and not make this mistake. The other lesson is that when a PR shows up with this kind of technical information attached to it, spend the 60 seconds it takes to Google for "lemire".