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.

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

findlast(_, ::Tuple[1..33+]) is not well #45117

Closed
JeffreySarnoff opened this issue Apr 28, 2022 · 2 comments
Closed

findlast(_, ::Tuple[1..33+]) is not well #45117

JeffreySarnoff opened this issue Apr 28, 2022 · 2 comments
Labels
performance Must go faster

Comments

@JeffreySarnoff
Copy link
Contributor

JeffreySarnoff commented Apr 28, 2022

julia> using BenchmarkTools

julia> symvector = collect(Symbol.("a"*string(i) for i=1:36));
julia> symtuple = Tuple(symvector);
julia> firstsym = :a1; lastsym = :a36;

julia> @btime findlast(==($lastsym), $symtuple);
  12.000 μs (72 allocations: 6.47 KiB)

these three are good

julia> @btime findfirst(==($firstsym), $symvector);
  2.400 ns (0 allocations: 0 bytes)

julia> @btime findlast(==($lastsym), $symvector);
  2.400 ns (0 allocations: 0 bytes)

julia> @btime findfirst(==($firstsym), $symtuple);
  2.200 ns (0 allocations: 0 bytes)

these lengths are informative

julia> @btime findlast(==($lastsym), $(symtuple[1:31]));
  4.200 ns (0 allocations: 0 bytes)

julia> @btime findlast(==($lastsym), $(symtuple[1:32]));
  120.415 ns (0 allocations: 0 bytes)

julia> @btime findlast(==($lastsym), $(symtuple[1:33]));
  10.300 μs (66 allocations: 5.53 KiB)
@JeffreySarnoff JeffreySarnoff changed the title findlast(==(x), ::Tuple[1..33+]) overallocates findlast(_, ::Tuple[1..33+]) is not well Apr 28, 2022
@KristofferC
Copy link
Member

KristofferC commented Apr 30, 2022

Could you be a bit more descriptive? What does " is not well" mean? It is usually a good idea in an issue to add a bit of descriptive text.

@JeffreySarnoff
Copy link
Contributor Author

right. The sense of it is that there are four cases and all are good given tuples with up to about 30 simple items. Three continue to behave nicely with larger tuples. One does not.

I was testing findfirst and findlast comparing their performance when given tuples and when given vectors with the same elements. In all cases the elements were single letter or two letter symbols (:a, :b, ..., :ab, :bc, ...). I had expected to see a performance advantage with tuples over vectors, and that it would be more obvious as lengths increased until the tuples became too long and then the vectors would have the advantage.

Further, I expected to see findfirst and findlast to be almost the same when given the same thing to find over. At the start, I tested findfirst to find the sixth item from the first (in the tuple and in the vector) and I tested findlast with sixth item from the last. This was just to ensure my benchmarking setup had no hidden issues. And I ran the four cases (findfirst in tuple, findfirst in vector, findlast in tuple, findlast in vector) on sequences of different lengths, all the while seeking the sixth from the first or from the last.

findfirst in tuple, findfirst in vector, and findlast in vector ran well and quite quickly found the targets throughout the range of lengths (24..40). I intended to take the lengths out more. but.

findlast seeking in a tuple with the same content and target as findlast seeking in a vector and relatively the same conditions as findfirst seeking in a tuple and in a vector (targeting the sixth from the end in the direction scanned) reported huge increases in allocations and time as the lengths got beyond 30..31.

findlast over a tuple of lengths 30, 31, 32 showed

30: 4.200 ns (0 allocations: 0 bytes)
31: 120.415 ns (0 allocations: 0 bytes)
32: 10.300 μs (66 allocations: 5.53 KiB)

and it keeps growing apace thereafter

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance Must go faster
Projects
None yet
Development

No branches or pull requests

3 participants