А знаете ли вы...

[thesz]

...что сборка мусора может улучшать работу кешейПричина проста - если сборщик идёт "в глубину", то для списка он скопирует сперва "голову" списка (элемент, хранящий два указателя - на головной элемент и на хвост), потом головной элемент (прямо рядос с "головой"), потом перейдёт к хвосту списка

Comments

[otake]

Если число элементов невелико, то разница несущественна, а если велико и производительность играет роль, нужно использовать hash tables.

[thesz]

Хэш-таблицы не параллельны, ибо принципиально изменяемы, это мы же вроде обсуждали.

[otake]

Хэш таблицы вполне "параллельны":

http://idav.ucdavis.edu/~dfalcant/research/hashing.php
fmcad10.iaik.tugraz.at/Papers/papers/12Session11/033Laarman.pdf
http://glaros.dtc.umn.edu/gkhome/node/73
www.waset.org/journals/waset/v61/v61-5.pdf

[thesz]

1. Вы сравните количество работы, необходимое для создания параллельной изменяемой структуры с количеством работы, необходимым для создания параллельной неизменяемой структуры. Во втором случае вообще ничегог делать не надо.

http://fprog.ru/2009/issue1/eugene-kirpichov-fighting-mutable-state/

2. Чтоыб понять глубину проблемы, попробуйте передать часть структуры (например, пересечение двух множеств на хеш таблицах) в параллельный поток. В случае неизменяемых структур используется разделение данных, в случае изменяемых - конструирование новой структуры.

[zelych]

Вот бы он деревья ещё в van Emde Boas складывал.

[thesz]

Ниже поделились ссылкой на такое исследование.

[mr_aleph]

люди дальше идут и хотят из "может улучшать" сделать "должен улучшать": исследуют адаптивное размещение (например: http://dl.acm.org/citation.cfm?id=286865 )

[thesz]

Спасибо.

А вот и PDF: http://research.microsoft.com/en-us/um/people/trishulc/papers/ismm_paper.pdf