Здравствуйте, watchmaker, Вы писали:

V>>Сугубо не согласен. В текущем аспекте — и генераторы и визитор и итераторы — все они эквивалентны по стоимости, если их рассматривать как абстракции архитектурного подхода. На с++ можно все эти три абстракции реализовать с нулевой одинаковой стоимостью для себжевого случая — перебора элементов хэш-таблицы.

W>Ну не совсем так.
W>Когда в стандарт C++ добавляли хеш-таблицы (которые стали std::unordered_map и std::unordered_set), то даже в самом proposal было замечено, что классические итераторы C++ — плохие, и эффективно проитерироваться по хеш-таблице ими не получается: мешает их устаревший интерфейс. Под "эффективно" тут подразумевается по сравнению с другими способами итерирования по содержимому (один из которых — это метод for_each у контейнера).
W>Смотри, например, раздел "Bucket Interface" предложения по хеш-таблицам.
W>А о том, как можно исправить итераторы C++ (несовместимым образом, конечно же) можно прочитать в другом предложении: Segmented Iterators and Hierarchical Algorithms (лучше даже с него начать).

Они имели ввиду несколько иное. Они предложили не то чтобы "тотальный подход, использовать всем!", а лишь "оптимизацию для некоторых специфических наполнений хэш-таблицы", при которых количество элементов в букете будет велико (то есть, наполнения при большом количестве коллизий между ключами). На практике такие наполнения встречаются редко. Обычно народ вполне грамотно подбирает хэш-функцию, обеспечивая минимум или даже полное отсутствие коллизий. За счет этого контейнер способен очень эффективно размазывать ключи по букетам. Таким образом, основная наполненность отдельно-взятого букета составляет 1 или ноль элементов, и лишь иногда (при коллизиях хэшфункции или коллизии размазывателя) получаются букеты с более чем одним элементом.

Насчет бумаги Segmented Iterators and Hierarchical Algorithms — обрати внимание, она опирается на ЭВМ 20-летней давности (упоминается 150 MHz MIPS R5000). Сегодняшние ЭВМ существенно отличаются по своим характеристикам, в частности, у них другая расфасовка стоимостей различных команд, за счет другой архитектуры (в основном из за кэширования ОЗУ и предсказание переходов). Я к тому, что заявленные в бумаге тайминги — они на современном железе будут несколько другие.

W>То есть классические итераторы в этом плане ущербны и действительно проигрывают по скорости другим альтернативам.

Да нет же :-
Никакой ущербности нет. Некоторая специфика есть, да. Например, если хэш таблица будет с большим количеством коллизий — то букетный перебор за счет этой особенности может выиграть. Но давай не будем рассматривать аномальные случаи.

С алгоритмической стороны, применение итераторов, генераторов, переборщика each_value, а теперь еще и упомянутый итераторБукета+итераторВнутриБукета — эквивалентны по затратам, так как имеют равные составы низкоуровневых инструкций в своей алгоритмике. Можно построить реализации любого из этих трех подходов и они будут одинаково быстро работать. Ну, конечно, с точностью до погрешности замеров, способностей оптимизатора кодогенерации и особенностей исполняющей машины.

Попробуй сам замерить, классические итераторы vs букет-итераторы, будешь удивлен.

Здравствуйте, watchmaker, Вы писали:

V>>Сугубо не согласен. В текущем аспекте — и генераторы и визитор и итераторы — все они эквивалентны по стоимости, если их рассматривать как абстракции архитектурного подхода. На с++ можно все эти три абстракции реализовать с нулевой одинаковой стоимостью для себжевого случая — перебора элементов хэш-таблицы.

W>Ну не совсем так.
W>Когда в стандарт C++ добавляли хеш-таблицы (которые стали std::unordered_map и std::unordered_set), то даже в самом proposal было замечено, что классические итераторы C++ — плохие, и эффективно проитерироваться по хеш-таблице ими не получается: мешает их устаревший интерфейс. Под "эффективно" тут подразумевается по сравнению с другими способами итерирования по содержимому (один из которых — это метод for_each у контейнера).
W>Смотри, например, раздел "Bucket Interface" предложения по хеш-таблицам.
W>А о том, как можно исправить итераторы C++ (несовместимым образом, конечно же) можно прочитать в другом предложении: Segmented Iterators and Hierarchical Algorithms (лучше даже с него начать).

Они имели ввиду несколько иное. Они предложили не то чтобы "тотальный подход, использовать всем!", а лишь "оптимизацию для некоторых специфических наполнений хэш-таблицы", при которых количество элементов в букете будет велико (то есть, наполнения при большом количестве коллизий между ключами). На практике такие наполнения встречаются редко. Обычно народ вполне грамотно подбирает хэш-функцию, обеспечивая минимум или даже полное отсутствие коллизий. За счет этого контейнер способен очень эффективно размазывать ключи по букетам. Таким образом, основная наполненность отдельно-взятого букета составляет 1 или ноль элементов, и лишь иногда (при коллизиях хэшфункции или коллизии размазывателя) получаются букеты с более чем одним элементом.

Насчет бумаги Segmented Iterators and Hierarchical Algorithms — обрати внимание, она опирается на ЭВМ 20-летней давности (упоминается 150 MHz MIPS R5000). Сегодняшние ЭВМ существенно отличаются по своим характеристикам, в частности, у них другая расфасовка стоимостей различных команд, за счет другой архитектуры (в основном из за кэширования ОЗУ и предсказание переходов). Я к тому, что заявленные в бумаге тайминги — они на современном железе будут несколько другие.

W>То есть классические итераторы в этом плане ущербны и действительно проигрывают по скорости другим альтернативам.

Да нет же

Никакой ущербности нет. Некоторая специфика есть, да. Например, если хэш таблица будет с большим количеством коллизий — то букетный перебор за счет этой особенности может выиграть. Но давай не будем рассматривать аномальные случаи.

С алгоритмической стороны, применение итераторов, генераторов, переборщика each_value, а теперь еще и упомянутый итераторБукета+итераторВнутриБукета — эквивалентны по затратам, так как имеют равные составы низкоуровневых инструкций в своей алгоритмике. Можно построить реализации любого из этих трех подходов и они будут одинаково быстро работать. Ну, конечно, с точностью до погрешности замеров, способностей оптимизатора кодогенерации и особенностей исполняющей машины.

Попробуй сам замерить, классические итераторы vs букет-итераторы, будешь удивлен.

[добавка]
Вычитал мотивировку G. Bucket Interface из пропозала... Они там ничего не говорят об ущербности итераторов для перебора элементов. Основное обоснование Bucket Interface — чтобы можно было контролировать распределение элементов по букетам (то есть, качество хэш-функции и подобные моменты, специфические для хэш-таблицы). О скоростях перебора — лишь только следующий кусок

if the iterators have an underlying segmented structure (as they do in existing singly linked list implementations), algorithms that exploit that structure, with an explicit nested loop, can be more efficient than algorithms that view the elements as a flat range

То есть, если некий пользовательский алгоритм переработки элементов будет способен эффективно использовать именно букетность представления данных вместо линейности — то он сможет это сделать. Обрати внимание, для получения бОльшей эффективности — у алгоритма переработки должна быть 'особенность' (an explicit nested loop), которая при сопряжении с букетным представлением может дать профит. Нет особенности — нет профита.