Оптимизируйте циклическое выполнение по большой строке, чтобы уменьшить выделение

#julia

Вопрос:

Я пытаюсь перебрать строку в Julia, чтобы разобрать ее. У меня есть DefaultDict внутри структуры, содержащий количество раз, когда я видел определенного персонажа.

 @with_kw mutable struct Metrics
    ...
    nucleotides = DefaultDict{Char, Int64}(0)
    ...
end

Я написал функцию для перебора строки и увеличения значения каждого символа в DefaultDict.

 function compute_base_composition(sequence::String, metrics::Metrics)
    for i in 1:sizeof(sequence)
        metrics.nucleotides[sequence[i]]  = 1
    end
end

Эта функция вызывается в цикле for, потому что мне нужно сделать это для нескольких строк (длина которых может составлять до 2 миллиардов символов). Когда я запускаю макрос @time, я получаю такой результат:

 @time compute_base_composition(sequence, metrics)
  0.167172 seconds (606.20 k allocations: 15.559 MiB, 78.00% compilation time)
  0.099403 seconds (1.63 M allocations: 24.816 MiB)
  0.032346 seconds (633.24 k allocations: 9.663 MiB)
  0.171382 seconds (3.06 M allocations: 46.751 MiB, 4.64% gc time)

Как вы можете видеть, для такой простой функции выделено много памяти. Я попытался изменить цикл for на что-то вроде for c in sequence , но это мало что изменило. Будет ли способ уменьшить их и ускорить выполнение функции?

1. Являются ли эти 4 строки результатом повторных запусков @time макроса без изменений кода? Я получаю аналогичные цифры только при первом запуске, и это составляет 99,1% времени компиляции (и, предположительно, выделения компилятора тоже). Последующие запуски выделяют только около 1 КБ.

2. функция compute_base_composition вызывается в цикле for, выходные данные @time относятся к первым вызовам этой функции.

3. Различные распределения во 2-4-м запусках странные, вы делаете разные строки за итерацию? Что касается моих 2 центов, я бы предположил, что 1) существует так много разных символов, что словарь часто расширяется и его приходится часто перераспределять в больший объем памяти, или 2) выделение символа sequence[i] -это выделение. 1) сомнительно, потому что в большинстве текстов используется только ASCII, и 2) очень сомнительно, потому что небольшие примитивные типы распределены по стеку.

4. Что вы подразумеваете под «с первых вызовов этой функции»? Возможно, вам также следует вставить цикл for здесь, минимальный пример, который повторяет эти распределения.

5. Вы смотрели на BioJulia? Вероятно, у него есть лучшие инструменты для выполнения такого рода задач.

Ответ №1:

Работа с байтами нет в символах юникода
Используйте Vector s не Dict s
Избегайте нетипизированных полей в контейнерах

 @with_kw struct MetricsB
    nucleotides::Vector{Int}=zeros(Int, 256)
end

function compute_base_composition(sequence::String, metrics::MetricsB)
    bs = Vector{UInt8}(sequence)
    for i in 1:length(bs)
        @inbounds metrics.nucleotides[bs[i]]  = 1
    end
end

И эталонный показатель с хорошим ускорением в 90 раз :

 julia> st = randstring(10_000_000);

julia> @time compute_base_composition(st, Metrics())
  1.793991 seconds (19.94 M allocations: 304.213 MiB, 3.33% gc time)

julia> @time compute_base_composition(st, MetricsB())
  0.019398 seconds (3 allocations: 9.539 MiB)

На самом деле вы можете почти полностью избежать распределения со следующим кодом:

 function compute_base_composition2(sequence::String, metrics::MetricsB)
    pp = pointer(sequence)
    for i in 1:length(sequence)
        @inbounds metrics.nucleotides[Base.pointerref(pp, i, 1)]  = 1
    end
end

а теперь:

 julia> @time compute_base_composition2(st, MetricsB())
  0.021161 seconds (1 allocation: 2.125 KiB)