Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Fix protect Array#map against concurrent mutation #15162

Open
wants to merge 6 commits into
base: master
Choose a base branch
from
Open

Fix protect Array#map against concurrent mutation #15162

wants to merge 6 commits into from

Conversation

straight-shoota
Copy link
Member

The optimized implementation of Array#map is vulnerable to concurrent mutation. This patch replaces it with a less efficient but safer variant. It's basically the same as Enumerable#map except that the new array's capacity is initialized with the current size.

Performance degrades by this less-efficient implementation, but it should be acceptable for the sake of safety.

A better performing alternative for highly optimized workloads is Slice#map.

10
old map_with_index  31.41M ( 31.84ns) (± 7.95%)  80.0B/op        fastest
new map_with_index  22.60M ( 44.25ns) (± 9.54%)  80.0B/op   1.39× slower

100
old map_with_index   6.65M (150.35ns) (± 7.28%)  480B/op        fastest
new map_with_index   3.55M (281.79ns) (± 5.26%)  480B/op   1.87× slower

100000
old map_with_index  16.64k ( 60.09µs) (± 6.02%)  391kB/op        fastest
new map_with_index   6.81k (146.93µs) (± 4.54%)  391kB/op   2.44× slower

100000000
old map_with_index  11.62  ( 86.04ms) (±10.12%)  381MB/op        fastest
new map_with_index   6.19  (161.46ms) (± 4.90%)  381MB/op   1.88× slower
Benchmark Code 
require "benchmark"

class Array
  def safe_map_with_index(offset = 0, & : T, Int32 -> U) forall U
    ary = Array(U).new(size)
    each_with_index(offset) { |e, i| ary << yield e, i }
    ary
  end
end

[
  Array(Int32).new(10, &.itself),
  Array(Int32).new(100, &.itself),
  Array(Int32).new(100_000, &.itself),
  Array(Int32).new(100_000_000, &.itself)
].each do |ary|
  puts ary.size

  Benchmark.ips do |bm|
    bm.report "old map_with_index" do
      ary.map_with_index { |e| e * 3}
    end
    bm.report "new map_with_index" do
      ary.safe_map_with_index { |e| e * 3}
    end
  end
  puts
end

Fixes #15161

@straight-shoota straight-shoota added kind:bug A bug in the code. Does not apply to documentation, specs, etc. performance topic:stdlib:collection labels Nov 5, 2024
@straight-shoota straight-shoota self-assigned this Nov 5, 2024
@BlobCodes
Copy link
Contributor

Is this fix really worth the reduced performance?

Java solves this by throwing a ConcurrentModificationException when modifying the amount of values in the array while using methods like map.
I think that could be an alternative solution.

@ysbaddaden ysbaddaden mentioned this pull request Nov 5, 2024
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees

@straight-shoota straight-shoota

Labels
kind:bug A bug in the code. Does not apply to documentation, specs, etc. performance topic:stdlib:collection
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Array#map is vulnerable to concurrent mutation
2 participants
@straight-shoota @BlobCodes