Я думаю, что это должно быть интересно в первую очередь как раз С/С++ программистам. Кому как ни нам создавать самые быстрые в мире программы?
Тем более, что возможность свободно управлять внутренней и внешней раскладкой объектов в памяти, и возможность использовать ассемблер — из мейнстримовых языков только у нас
Получается, что можно реализовать почти-STL-set c оптимизацией Binary Search и почти-STL-map (с немного не таким интерфейсом, без ссылок на pair) с оптимизацией Binary Search и Data Splitting ?
Re[2]: RAM - не RAM, или Cache-Conscious Data Structures
А>Получается, что можно реализовать почти-STL-set c оптимизацией Binary Search и почти-STL-map (с немного не таким интерфейсом, без ссылок на pair) с оптимизацией Binary Search и Data Splitting ?
С почти таким интерфейсом определенно можно. Хотя я не думаю, что для "специализированной" структуры данных имеет большой смысл стремиться к "общему" интерфейсу. Например, при общем интерфейсе придётся перестраивать всю структуру после каждой модификации. Более же разумно предусмотреть интерфейс для "пакетных" изменений, т.е. меняем что-то, потом вручную вызываем rebuild().
R>Я думаю, что это должно быть интересно в первую очередь как раз С/С++ программистам. Кому как ни нам создавать самые быстрые в мире программы?
R>Тем более, что возможность свободно управлять внутренней и внешней раскладкой объектов в памяти, и возможность использовать ассемблер — из мейнстримовых языков только у нас
Может кому будет так же интересно почитать про многопоточность:
Здравствуйте, remark, Вы писали:
R>Здравствуйте, Аноним, Вы писали:
А>>Здравствуйте, remark, Вы писали:
R>>>Кросс-пост в Философии программирования: R>>>http://gzip.rsdn.ru/forum/message/2929998.1.aspx
А>>Получается, что можно реализовать почти-STL-set c оптимизацией Binary Search и почти-STL-map (с немного не таким интерфейсом, без ссылок на pair) с оптимизацией Binary Search и Data Splitting ?
R>С почти таким интерфейсом определенно можно. Хотя я не думаю, что для "специализированной" структуры данных имеет большой смысл стремиться к "общему" интерфейсу. Например, при общем интерфейсе придётся перестраивать всю структуру после каждой модификации. Более же разумно предусмотреть интерфейс для "пакетных" изменений, т.е. меняем что-то, потом вручную вызываем rebuild().
Data Splitting тоже не понятно как запихать в общий интерфейс.
Re[4]: RAM - не RAM, или Cache-Conscious Data Structures
От:
Аноним
Дата:
27.04.08 11:57
Оценка:
Здравствуйте, remark, Вы писали:
R>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, Аноним, Вы писали:
А>>>Здравствуйте, remark, Вы писали:
R>>>>Кросс-пост в Философии программирования: R>>>>http://gzip.rsdn.ru/forum/message/2929998.1.aspx
А>>>Получается, что можно реализовать почти-STL-set c оптимизацией Binary Search и почти-STL-map (с немного не таким интерфейсом, без ссылок на pair) с оптимизацией Binary Search и Data Splitting ?
R>>С почти таким интерфейсом определенно можно. Хотя я не думаю, что для "специализированной" структуры данных имеет большой смысл стремиться к "общему" интерфейсу. Например, при общем интерфейсе придётся перестраивать всю структуру после каждой модификации. Более же разумно предусмотреть интерфейс для "пакетных" изменений, т.е. меняем что-то, потом вручную вызываем rebuild().
Возможно тут как-то можно найти оптимальное правило, когда автоматически перебалансировать. Хотя и с ребилдом ничего.
Может, тут оптимально будет применить не-двоичное дерево поиска, т.е. рассматривать как узлы такие группы из элементов, которые оптимально помещаются в кэш ? Вот как в NTFS узлы содержат столько элементов, чтобы поместится в кластер.
R>Data Splitting тоже не понятно как запихать в общий интерфейс.
У map же поиск идёт только по key, вот key и будет hot. Конечно, убрать у мэпа всё что возращает ссылки на пары, вроде заменить Type& operator[] на Type operator[] и оставить у итератора только i->second, убрав (*i).second.
Просто хотелось бы, чтобы куча имеющегося STL кода была оптимизируема, когда это будет надо
Re[5]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, Аноним, Вы писали:
R>>>С почти таким интерфейсом определенно можно. Хотя я не думаю, что для "специализированной" структуры данных имеет большой смысл стремиться к "общему" интерфейсу. Например, при общем интерфейсе придётся перестраивать всю структуру после каждой модификации. Более же разумно предусмотреть интерфейс для "пакетных" изменений, т.е. меняем что-то, потом вручную вызываем rebuild().
А>Возможно тут как-то можно найти оптимальное правило, когда автоматически перебалансировать.
Проблема в том, что нельзя просто отложить rebuild(), нельзя просто добавить элемент "в конец" без rebuild(). Тогда будет нарушен порядок, и соотв. поиск будет выдавать неправильный результат.
А>Может, тут оптимально будет применить не-двоичное дерево поиска, т.е. рассматривать как узлы такие группы из элементов, которые оптимально помещаются в кэш ? Вот как в NTFS узлы содержат столько элементов, чтобы поместится в кластер.
Хммм... В принципе факт, что при двоичном дереве в каждой кэш-линии остаётся 1 неиспользованный элемент, меня немного тревожит. Но с троичном деревом, или четверичным деревом, вроде не получается лучше. Тем более, чем больше арность дерева, тем меньше переходов будет разрешено каждой кэш-линией, читай — меньше элементов будет использовано из каждой кэш-линии. Т.е. возвращаемся туда, откуда ушли.
Re[6]: RAM - не RAM, или Cache-Conscious Data Structures
От:
Аноним
Дата:
27.04.08 14:25
Оценка:
Здравствуйте, remark, Вы писали:
R>Хммм... В принципе факт, что при двоичном дереве в каждой кэш-линии остаётся 1 неиспользованный элемент, меня немного тревожит. Но с троичном деревом, или четверичным деревом, вроде не получается лучше. Тем более, чем больше арность дерева, тем меньше переходов будет разрешено каждой кэш-линией, читай — меньше элементов будет использовано из каждой кэш-линии. Т.е. возвращаемся туда, откуда ушли.
Как раз B*-trees в NTFS (и других ФС) применены чтобы найти файл в каталоге прочитав минимально возможное число кластеров, т.к. чтение кластера дорогая операция и кластер читается полностью.
Может мы о разном говорим ? Я об этом здесь.
А вообще хешмэп/хешсет наверно всё равно быстрее будет.
Re[5]: RAM - не RAM, или Cache-Conscious Data Structures
прошу прощения, но я не вижу в этом большого смысла, как и remark, в по 2м причинам
1. в 99% случаев такие оптимизации не нужны ни одной программе. они просто работают с таким кол-вом данных, что самый медленный алгоритм поиска будет незаметен. в первую очередь это касается десктоп-аппликух
2. Все эти оптимизации стоят дорого, тк у нас не managed-код, и все они зашиваются на этапе компиляции. А значит будет работать на интел/амд и тд. Желательно
, чтобы работало без разбросов, средненько. С такими оптимизациями можно влететь на одной из платформ.
Так вот хочется, чтобы по виду это отличалось от STL.
Re[7]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, Аноним, Вы писали:
R>>Хммм... В принципе факт, что при двоичном дереве в каждой кэш-линии остаётся 1 неиспользованный элемент, меня немного тревожит. Но с троичном деревом, или четверичным деревом, вроде не получается лучше. Тем более, чем больше арность дерева, тем меньше переходов будет разрешено каждой кэш-линией, читай — меньше элементов будет использовано из каждой кэш-линии. Т.е. возвращаемся туда, откуда ушли.
А>Как раз B*-trees в NTFS (и других ФС) применены чтобы найти файл в каталоге прочитав минимально возможное число кластеров, т.к. чтение кластера дорогая операция и кластер читается полностью. А>Может мы о разном говорим ? Я об этом здесь.
Т.е. если в кэш-линию помещается 8 элементов, то мы кладём в неё 8 элементов "одного уровня", и делаем у неё 9 дочерних кэш-линий. Тогда поиск будет за log8(N). Я правильно понял? Надо подумать.
А>А вообще хешмэп/хешсет наверно всё равно быстрее будет.
Re[8]: RAM - не RAM, или Cache-Conscious Data Structures
От:
Аноним
Дата:
27.04.08 19:12
Оценка:
Здравствуйте, remark, Вы писали:
R>Т.е. если в кэш-линию помещается 8 элементов, то мы кладём в неё 8 элементов "одного уровня", и делаем у неё 9 дочерних кэш-линий. Тогда поиск будет за log8(N). Я правильно понял? Надо подумать.
Да, поняли Вы правильно.
А>>А вообще хешмэп/хешсет наверно всё равно быстрее будет.
R>В целом, да. Поиск в хэше — О(1).
Ну тогда пока конвертация ассоциативных контейнеров в Cache-Conscious Data Structures не имеет большого смысла. Если map нельзя заменить на hash_map, то это скорее всего потому, что используются диапазоны вроде equal_range или begin..lower_bound, а не отдельные элементы, а значит рассматриваемая оптимизация не подходит.
Re[6]: RAM - не RAM, или Cache-Conscious Data Structures
От:
Аноним
Дата:
27.04.08 19:18
Оценка:
Здравствуйте, Константин Л., Вы писали:
КЛ>[]
В десктоп приложении, в разработке которого участвую, уже ощутилась замена map на hash_map, так что не у всех десктоп приложений мало данных. Но с тем что именно такая оптимизация, скорее всего, не имеет смысла я уже согласился — здесь
R>>Я думаю, что это должно быть интересно в первую очередь как раз С/С++ программистам. Кому как ни нам создавать самые быстрые в мире программы?
R>>Тем более, что возможность свободно управлять внутренней и внешней раскладкой объектов в памяти, и возможность использовать ассемблер — из мейнстримовых языков только у нас
