Сообщение Re[8]: Оцените решение задачи от 16.10.2014 13:19
Изменено 16.10.2014 13:21 slava_phirsov
Здравствуйте, smeeld, Вы писали:
S>Что до промахов в кеше из-за раскиданности нод списка, во всех нормальных
S>системах, ноды для списков выделяются из некоторого непрерывного массива,
S>кеша специализированного аллокатора. Так что никакой раскиданности.
Вот мне тоже так думается, но у wathcmaker-а был еще один козырь — зависимость по данным. Компилятор может (хотя и не должен) развернуть цикл обхода массива и (в суперскалярной арх-ре) практически параллельно выполнять операции над группой элементов массива. Отдельные коллеги, (напр. Касперски в одной из своих книг) уверяют, что это дает существенную разницу.
P.S. Кроме того, для связного списка нет никакой гарантии, что последовательные элементы списка располагаются в памяти последовательно, что как бы снижает эффективность выделения памяти для узлов списка из одного пула.
S>Что до промахов в кеше из-за раскиданности нод списка, во всех нормальных
S>системах, ноды для списков выделяются из некоторого непрерывного массива,
S>кеша специализированного аллокатора. Так что никакой раскиданности.
Вот мне тоже так думается, но у wathcmaker-а был еще один козырь — зависимость по данным. Компилятор может (хотя и не должен) развернуть цикл обхода массива и (в суперскалярной арх-ре) практически параллельно выполнять операции над группой элементов массива. Отдельные коллеги, (напр. Касперски в одной из своих книг) уверяют, что это дает существенную разницу.
P.S. Кроме того, для связного списка нет никакой гарантии, что последовательные элементы списка располагаются в памяти последовательно, что как бы снижает эффективность выделения памяти для узлов списка из одного пула.
Re[8]: Оцените решение задачи
Здравствуйте, smeeld, Вы писали:
S>Что до промахов в кеше из-за раскиданности нод списка, во всех нормальных
S>системах, ноды для списков выделяются из некоторого непрерывного массива,
S>кеша специализированного аллокатора. Так что никакой раскиданности.
Вот мне тоже так думается, но у wathcmaker-а был еще один козырь — зависимость по данным. Компилятор может (хотя и не должен) развернуть цикл обхода массива и (в суперскалярной арх-ре) практически параллельно выполнять операции над группой элементов массива. Отдельные коллеги, (напр. Касперски в одной из своих книг) уверяют, что это дает существенную разницу.
P.S. Кроме того, для связного списка нет никакой гарантии, что последовательные элементы списка располагаются в памяти последовательно, что как бы снижает эффект выделения памяти для узлов списка из одного пула.
S>Что до промахов в кеше из-за раскиданности нод списка, во всех нормальных
S>системах, ноды для списков выделяются из некоторого непрерывного массива,
S>кеша специализированного аллокатора. Так что никакой раскиданности.
Вот мне тоже так думается, но у wathcmaker-а был еще один козырь — зависимость по данным. Компилятор может (хотя и не должен) развернуть цикл обхода массива и (в суперскалярной арх-ре) практически параллельно выполнять операции над группой элементов массива. Отдельные коллеги, (напр. Касперски в одной из своих книг) уверяют, что это дает существенную разницу.
P.S. Кроме того, для связного списка нет никакой гарантии, что последовательные элементы списка располагаются в памяти последовательно, что как бы снижает эффект выделения памяти для узлов списка из одного пула.