Направление итерации массива Bash и производительность

Может ли кто-нибудь объяснить, в чем причина серьезного замедления при повторении массивов bash в обратном направлении?

Пример:

time bash -c 'arr=();for i in {1..100000}; do arr+=( $i );done; echo "Straight"; i=0;while (( $i < 100000 )); do current_element=${arr[$i]}; ((i++));done'

Straight

real    0m0.270s
user    0m0.269s
sys 0m0.002s

time bash -c 'arr=();for i in {1..100000}; do arr+=( $i );done; echo "Reverse"; i=99999;while (( $i > 0 )); do current_element=${arr[$i]}; ((i--));done'

Reverse

real    0m25.569s
user    0m25.589s
sys 0m0.008s

Также

${arr[i-1]} + ${arr[i]} 

намного быстрее, чем

${arr[i]} + ${arr[i-1]}

Спасибо за ваше время.

Редактировать:

Баш --версия

GNU bash, версия 4.3.42(1)-выпуск (x86_64-redhat-linux-gnu)


person dgeorgiev    schedule 15.09.2015    source источник
comment
очень интересно. Я подозреваю, что только кто-то, хорошо знакомый с реализацией bash, сможет дать ответ. Для тех, кто надеется на интим: git.savannah.gnu.org/cgit/ bash.git/дерево   -  person glenn jackman    schedule 15.09.2015
comment
Пожалуйста, добавьте версию bash к вашему вопросу.   -  person Cyrus    schedule 15.09.2015
comment
Массивы bash на самом деле являются двусвязными списками, поэтому наивное ожидание состоит в том, что {$arr[$i]} должна быть операцией O(n), независимо от того, увеличивается или уменьшается i. Похоже, что может быть какая-то оптимизация кэширования, которая ускоряет доступ для увеличения i. Это имеет смысл, учитывая, что основной вариант использования — передать содержимое массива в качестве позиционных параметров.   -  person chepner    schedule 15.09.2015


Ответы (1)


Нашел информацию по этому поводу.

Согласно http://www.tldp.org/LDP/abs/html/arrays.html

Массивы в Bash представляют собой (циклически) связанные списки строкового типа (char *).

Я предполагаю, что это означает, что переданные элементы каждый раз ищутся с начала массива, отсюда и замедление. (например: если мы находимся в i, чтобы добраться до i-1, мы должны начать поиск с 0)

Также нашел связанный пост с дополнительной информацией по этому вопросу: http://spencertipping.com/posts/2013.0814.bash-is-irrecoverably-broken.html

person dgeorgiev    schedule 16.09.2015