Here is a simple implementation of a two-pointer technique for sorted arrays: function f(xs, ys) i_begin, i_end = firstindex(xs), firstindex(xs) map(ys) do y i_begin = something( findnext(x -> x >= y, xs, i_begin), lastindex(xs) + 1 ) i_end = something( findnext(x -> x > y, …

I think you are hitting performance of captured variables in closures · Issue #15276 · JuliaLang/julia · GitHub , because you create anonymous functions for the findnext call.

The issue remains even without anonymous functions in findnext: function f(xs, ys) i_begin, i_end = firstindex(xs), firstindex(xs) ys_new = map(ys) do y i_begin = something( findnext(>=(y), xs, i_begin), lastindex(xs) + 1 ) i_end = something( findnext(>(y), xs, max(i_begin, …

It is still the same issue, but I misidentified the anonymous function. It is the one created by the do block. Here is non-allocating version (EDIT: of a similar function). function f(xs, ys) local ys_new i_begin, i_end = firstindex(xs), firstindex(xs) let xs = xs, ys = ys, i_begin = i_begin,…

Your code doesn’t do the same calculations: it never modifies i_begin and i_end. Each findnext should start at the index i_begin from the previous iteration.

Ah sorry, you are right. Then do what Kristoffer suggested.

Thanks, this works perfectly well! The final solution looks like this: function f(xs, ys) ix = Ref(firstindex(xs):firstindex(xs)) map(ys) do y i_begin = something( findnext(x -> x >= y, xs, first(ix[])), lastindex(xs) + 1 ) i_end = something( findnext(x -> x > y, xs, max(i_b…

Cannot achieve type-stability and get rid of allocations

General Usage

kristoffer.carlsson August 8, 2020, 11:19am 6

You can wrap those variables in Ref s that you then mutate instead of rebinding.

Advanced iteration interface in Julia

Topic		Replies	Views
Type unstable function because same variable name used twice General Usage type , code_warntype	10	1437	April 8, 2021
Type instability when using map with closures General Usage type-stability , closure , map	3	424	July 12, 2023
Why isn't a simple map type stable? General Usage	2	609	August 26, 2021
Type stability with variable arguments Performance type-stability	16	1473	January 16, 2022
Type stability on Arrays of Arrays in nested for loops? Performance question , arrays , type-stability	16	959	February 20, 2021

Cannot achieve type-stability and get rid of allocations

Related topics