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

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

PC_>>>Разные Б деревья в плане скорости поиска/вставки не интересны.
S>> Ну почему же. Б+ деревья на больших данных немного уступают Хэш таблицам. При примененийй данных типа курсора

PC_>На больших обьемах данных у хештаблиц коллизии ростут в экспоненциальном порядке.
В этой же статье есть Хэш таблица массив данных которых поделен на две части во второй хранятся коллизии и при заполнении которой размер таблицы увеличиваются в 2 раза и перезаполняются. Соотношение при полном заполнении заполненных в первой части к количеству в кчасти хранения коллизий постоянно. Кстати в нетовской реализации существует две таблицы в первой храняться данные ссылающиеся на вторую таблицу. Коллиции соединяюся односвязным списком как и свободные места. И по сути индентичен моей таблице. Перестройка таблицы происходит при полном заполнении таблицы. Первый нетовский вариант был весьма неудачен.

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

S>Здравствуйте, PC_2, Вы писали:
PC_>>Теперь чисто визуально, сколько нужно первой реализации выполнить процессорных комманд, сделать дополнительных вызовов функций, копирований и тд
S> Ну я предлагал использовать Хэш таблицу для ключей в котором хранится ключ и страница Б+ дерева Что бы производить поиск не по дереву а на странице.

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

S>Но это не суть. Проблема при увеличении объемов данных не попадающих в Кэш процессора сильно уже зависит от медленной памяти. А соотношение времени вставки поиска Б+ деревья и Хэш таблицы остаются константными.

Константно медленными.

S>Кстати если видел реализацию NavigateOrInsertDefault то там запоминаентся текущая позиция и при изменении значения вторичный поиск не производится. А по поводу выборки Б+ деревьев, то это прохождение по масииву.

Обычная оптимизация, что называется первое что пришло в голову.
Догадываюсь что это работает только для последовательного доступа по ключам.
Random выборки ближе к реалиям и более интересны.

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

Было бы интересно потестировать Вашу реализацию, на двух простеньких бенчмарках.
Результаты бенчмарков здесь http://www.sql.ru/blogs/stebelek/1267, код бенчмарков можно найти в этой теме на
преведущих страницах.

Пока что майкрософтовские красно-черные деревья отстали в среднем в 20-30 раз по каждой позиции.
И на 20%-30% по памяти.

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


PC_>Все эти алгоритмические симбиозы, добавляют процессорных комманд. Если Вы решили использовать хештаблицу,
PC_>то отработка хешфункции для строки будет вам стоить до 50 наносекунд и пару сотен процессорных комманд.
PC_>Еще добавите какихто ифов, какойто счетчик в цикле, лишний переход по указателю функции и снова десятки наносекунд,
PC_>десятки процессорных комманд. Потом все суммируете и получаете результат.
Да все это пшик по сравнению к доступу к медленной памяти.

PC_>Думаю эта реализация может себя оправдать, например при работе с диском, когда временем процессора можно
PC_>принебречь по сравнению с временем работы доступа к диску.
Обычно данные кэширутся даже на файловом уровне.
S>>Но это не суть. Проблема при увеличении объемов данных не попадающих в Кэш процессора сильно уже зависит от медленной памяти. А соотношение времени вставки поиска Б+ деревья и Хэш таблицы остаются константными.

PC_>Константно медленными.
Да нет где то в 4 раза Б+ деревья медленнее хэш таблиц.
S>>Кстати если видел реализацию NavigateOrInsertDefault то там запоминаентся текущая позиция и при изменении значения вторичный поиск не производится. А по поводу выборки Б+ деревьев, то это прохождение по масииву.

PC_>Обычная оптимизация, что называется первое что пришло в голову.
PC_>Догадываюсь что это работает только для последовательного доступа по ключам.
PC_>Random выборки ближе к реалиям и более интересны.
Нужно отталкиваться от реалий. Я уже давно занимаюсь БД а там есть и рандомные слияния с использованием ХЭШ таблиц, и джойны с использованием отсортированных данных. Но если Б+ деревья отстают от хэш таблиц в 4 раза то сокращение в 2 раза с использованием NavigateOrInsertDefault уже становится соизмеримыми. Но это иследования 8 летней давности. Сейчас и изменением сорости памяти может сильно поменяться. Пока 1С мое все.

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

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

PC_>Было бы интересно потестировать Вашу реализацию, на двух простеньких бенчмарках.
PC_>Результаты бенчмарков здесь http://www.sql.ru/blogs/stebelek/1267, код бенчмарков можно найти в этой теме на
PC_>преведущих страницах.

PC_>Пока что майкрософтовские красно-черные деревья отстали в среднем в 20-30 раз по каждой позиции.
PC_>И на 20%-30% по памяти.
Там есть реализация Б+ деревьев. Там переделывать вроде ничего не надо попробуй ее. Все таки красночерные деревья достаточно медленные я их сравнивал правда давно. Прежде всего из-за скорости поиска. Так оптимальны на тот момент для интов размер страницы был равен 64 элемента. А вот страницы верхнего уровня увеличены до 256 можно было и больше и связано именно с поиском. Чем больше страница тем быстрее поиск.

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

S>Да все это пшик по сравнению к доступу к медленной памяти.

Я думаю ин-мемори бенчмарки должни все расставлять на свои места. Сложно анализировать алгоритмы
на квантовом уровне. У меня если рандом ключи, доступ 40 наносекунд, а если последовательно то 3-5 наносекунд.
Тоже творится и в деревьях, ток им еще по нолику минимум дописывать.
Процессор довольно сложная штука, с блоком предсказаний, разной по тяжести процессорных комманд,
разной работой кешей процессора, доступом к ОЗУ и тд.
Вообщем то что намерял — опубликовал.

S> Да нет где то в 4 раза Б+ деревья медленнее хэш таблиц.
А у меня алгоритм еще в 3-4 раза быстрее, Хештаблиц, итого Б деревья отстают как раз std::map овские 20-30 раз.

S> Нужно отталкиваться от реалий. Я уже давно занимаюсь БД а там есть и рандомные слияния с использованием ХЭШ таблиц, и джойны с использованием отсортированных данных. Но если Б+ деревья отстают от хэш таблиц в 4 раза то сокращение в 2 раза с использованием NavigateOrInsertDefault уже становится соизмеримыми. Но это иследования 8 летней давности. Сейчас и изменением сорости памяти может сильно поменяться. Пока 1С мое все.

1С не интересно
Возвращайтесь к фундаментальным алгоритмам, прогресс не стоит на месте

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

S> Там есть реализация Б+ деревьев. Там переделывать вроде ничего не надо попробуй ее.

Мне не интересно мерять.
Нет никакой интриги, всеравно медленно.

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

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

S>>Да все это пшик по сравнению к доступу к медленной памяти.

PC_>Я думаю ин-мемори бенчмарки должни все расставлять на свои места. Сложно анализировать алгоритмы
PC_>на квантовом уровне. У меня если рандом ключи, доступ 40 наносекунд, а если последовательно то 3-5 наносекунд.
PC_>Тоже творится и в деревьях, ток им еще по нолику минимум дописывать.
PC_>Процессор довольно сложная штука, с блоком предсказаний, разной по тяжести процессорных комманд,
PC_>разной работой кешей процессора, доступом к ОЗУ и тд.
PC_>Вообщем то что намерял — опубликовал.

Там немного другие параметы. Первое это доступ к данным которые находятся в Кэше процессора. Самый быстрый вариант.
Второе это когда данные не попадают в Кэш, но находятся рядом за счет использования чтения памяти DDR и ширины шины памяти.
Поэтому на больших данных быстрее может быть моя Хэш таблица а не нетовская. Там нужно делать как минимум два перехода в моей минимум один раз.

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


S>> Да нет где то в 4 раза Б+ деревья медленнее хэш таблиц.
PC_>А у меня алгоритм еще в 3-4 раза быстрее, Хештаблиц, итого Б деревья отстают как раз std::map овские 20-30 раз.

Кстати когда я написал статью и показал, что моя хэш таблица может быть в 4 раза быстрее стандартной это мало кого заинтересовало.
Опять же моя хэш таблица быстрее текущей в те же 2 раза за счет курсрности. Так что твоя хэш таблица быстрее ненамного моей. А люди будут пользоватся стандартными. Хотя если честно мне интересен принцип такого ускорения.

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

Вам нужно перемерять свой алгоритм.
Дело в том, что если Вы тестировали его еще на первых версиях Фреймворка, то там
были малооптимизированые версии. Я вот гонял последнюю их хештаблицу в фреймворке 3.5,
то эта работает весьма прилично. Скажем так, последняя ихняя версия отстала от моей всего в 2-3 раза.
Ну и плюс у меня сортированные ключи, тоесть можно делать выборки по диапазону.
А в майкрософтовской — нет. Тоесть функционал неэквивалентен, но по скорости весьма прилично.

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

S> Кстати когда я написал статью и показал, что моя хэш таблица может быть в 4 раза быстрее стандартной это мало кого заинтересовало.
S>Опять же моя хэш таблица быстрее текущей в те же 2 раза за счет курсрности. Так что твоя хэш таблица быстрее ненамного моей. А люди будут пользоватся стандартными. Хотя если честно мне интересен принцип такого ускорения.

Ну и плюс С# vs C++. Такие низкоуровневые вещи не имеем смысла писать на управляемом языке.

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

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

PC_>Вам нужно перемерять свой алгоритм.
PC_>Дело в том, что если Вы тестировали его еще на первых версиях Фреймворка, то там
PC_>были малооптимизированые версии. Я вот гонял последнюю их хештаблицу в фреймворке 3.5,
PC_>то эта работает весьма прилично. Скажем так, последняя ихняя версия отстала от моей всего в 2-3 раза.
PC_>Ну и плюс у меня сортированные ключи, тоесть можно делать выборки по диапазону.
PC_>А в майкрософтовской — нет. Тоесть функционал неэквивалентен, но по скорости весьма прилично.

Так я про 3.5 и говорю. Они по всем алгоритмам схожи с моей. Я даже сравнивал их. Моя быстрее там, где нет лишнего рехеша, т.к. моя перезаполняется при заполнении части таблицы с коллизиями, а нетовская при полном заполнении. Ну и моя была раньше.
Если использовать запоминание позиции при поиске, то при модификации время уменьшается в 2 раза.
На больших данных не попадающих в кэш моя таблица тоже начинает быстрее работать, т.к. данные находятся рядом.
По поводу сравнения интов и строк. Когда мы начинаем сравнивать строки( а это основная масса данных), то разница в скорости быстро сокращается, т.к. основное время уходит на сравнение строк и хэширование строки.

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

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

S>> Кстати когда я написал статью и показал, что моя хэш таблица может быть в 4 раза быстрее стандартной это мало кого заинтересовало.
S>>Опять же моя хэш таблица быстрее текущей в те же 2 раза за счет курсрности. Так что твоя хэш таблица быстрее ненамного моей. А люди будут пользоватся стандартными. Хотя если честно мне интересен принцип такого ускорения.

PC_>Ну и плюс С# vs C++. Такие низкоуровневые вещи не имеем смысла писать на управляемом языке.
А начем мне писать если я использую C#. Там кстати из за эффекта оптимизации для сборки мусора старших поколений, идет лишние действия по запоминанию этих объектов которые сильно тормозят процесс после сборки мусора. Во второй версии NET они подправили, но не сильно, а в 4 уже не тестил http://rsdn.ru/forum/dotnet/415352.1.aspx

Автор: Serginio1
Дата: 20.10.03

Поэтому в Net предпочтительней использовать массивы а не списки.

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

S> Так я про 3.5 и говорю. Они по всем алгоритмам схожи с моей. Я даже сравнивал их. Моя быстрее там, где нет лишнего рехеша, т.к. моя перезаполняется при заполнении части таблицы с коллизиями, а нетовская при полном заполнении. Ну и моя была раньше.
S>Если использовать запоминание позиции при поиске, то при модификации время уменьшается в 2 раза.
S>На больших данных не попадающих в кэш моя таблица тоже начинает быстрее работать, т.к. данные находятся рядом.
S>По поводу сравнения интов и строк. Когда мы начинаем сравнивать строки( а это основная масса данных), то разница в скорости быстро сокращается, т.к. основное время уходит на сравнение строк и хэширование строки.

Попробуйте сделать вот такой бенчмарк.
http://www.sql.ru/blogs/stebelek/1269

Тест не должен быть рафинированным, под курсор.
Должни рассматриватся в комплексе несколько параметров поиск/вставка/память,
природа ключей — рандом, последовательные.

ЗЫ: Скачал Ваш проект, к сожалению он не открылся на двух машинах (студия экспресс и ультимейт).
Просит сконвертировать, потом какието ошибки и отказывается открывать. Нужен фикс наверное.

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

S> А начем мне писать если я использую C#.

Пишите на Си. Я тоже по основному месту работы уж 10 лет пишу как под дот нет,
но этот проект просто обязан быть на чистом Си/Си++

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



PC_>ЗЫ: Скачал Ваш проект, к сожалению он не открылся на двух машинах (студия экспресс и ультимейт).
PC_>Просит сконвертировать, потом какието ошибки и отказывается открывать. Нужен фикс наверное.
А можно на ты. Устал я от "Вы" и не ощущаю себя. Этот проект писался под бету VS 2005. Которую они потом сильно поменяли к релизу.
Там надо скопировать исходники и на них потестить. Я то программирую на 1С, а C# это так развлечение.

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

S>Там надо скопировать исходники и на них потестить. Я то программирую на 1С, а C# это так развлечение.

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

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

На счет применения. Думаю одним из простых, на базе кластера из хешареев можно было бы построить
фулл текст энжин, аля Сфинкс, только вот скорость индексирования у него была бы не 10-15 мегабайт
на поток, а скажем 50-100 мб и мощность поиска по словоформам около миллиона в секунду.
Както так, больше пока ничего не придумывается.

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

PC_>Тест не должен быть рафинированным, под курсор.

А рафинирование под инт? Я вот хочу любой объект, любой структуры. Например — строка рандомной длины. От байта до мегабайта. Для реальных задач — пойдет. Или, может, кастомную структуру?

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

E__>А рафинирование под инт? Я вот хочу любой объект, любой структуры. Например — строка рандомной длины. От байта до мегабайта. Для реальных задач — пойдет. Или, может, кастомную структуру?

Посмотрите внимательней реализацию Джуди да и любой Хештаблицы.
По сути Hastable<String,String> = Простая хешфункция + Hastable<Int,Int> + Списки коллизий

Я правда хочу придумать что-то поинтеллектуальней.

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

PC_>Есть еще вырожденный вариант для 32 битных ключей

PC_>

PC_>inline uint getValueByKeyInt32(uint key)
PC_>{
PC_>    return (uint)pInfoRoot->pBlockInfos[key&0xFFFF]->pBlockInfos[key>>16];
PC_>}
PC_>

судя по коду нужно зарезервировать 16 gb памяти, чтобы адресовать все доступные ключи

65536 * 65535 * sizeof(uint)