| Сейчас на форуме: zds (+5 невидимых) |
 |
eXeL@B —› Программирование —› Lock-Free деревья |
| Посл.ответ | Сообщение |
|
|
Создано: 19 декабря 2013 23:11 · Личное сообщение · #1 Кто нибудь кодил не блокирующие деревья? Интересно было бы глянуть реализации. ----- have a nice day  |
|
|
Создано: 19 декабря 2013 23:46 · Личное сообщение · #2 google полон реализациями чем не устраивают? |
|
|
Создано: 19 декабря 2013 23:47 · Личное сообщение · #3 Я пилил в том году 2ух метровые деревья на новый год. Реализация... 8 лет назад их посадить. | Сообщение посчитали полезным: plutos |
|
|
Создано: 20 декабря 2013 00:09 · Личное сообщение · #4 ----- Give me a HANDLE and I will move the Earth. |
|
|
Создано: 20 декабря 2013 00:29 · Личное сообщение · #5 На новых процах Haswell по этой части . Любой алгоритм становится lock-free с помощью простой обертки в транзакцию, вообще без изменения кода. ----- PGP key |
|
|
Создано: 25 декабря 2013 18:22 · Поправил: Nimnul · Личное сообщение · #6 reversecode Гугл полон не реализациями, а разговорами о реализациях, а это большая разница. Я нашел только красно-черные деревья и честно говоря говно-реализации. Я уже не говорю что красно черные деревья хуже АВЛ по скорости всех основных функций. Поэтому я даже тестить не стал, вполне вероятно что там очень низкий прирост на каждый поток. ntldr Чтож это очень круто звучит. Но реально нужно делать тесты, что бы аргументированно делать выводы. Я сам сделал десяток лок-фри деревьев, и каждый раз мне казалось что это возможный потолок... Поэтому может оказаться, что эти самые транзакции хавают очень много, так много что это уже сравнимо с решением на семафоре... Статья от этой осени, когда это дойдет до реальных компиляторов? Не буду же я руками префиксы втыкать.  Тенденция мне явно нравится, давно пора решать эти проблемы аппаратно.plutos Толковый ответ, почитаю. ----- have a nice day |
|
|
Создано: 25 декабря 2013 20:51 · Личное сообщение · #7 Nimnul пишет: эти самые транзакции хавают очень много Вся прелесть этих транзакций, что в оптимистичном случае они НИЧЕГО не хавают. Работает это так: процессор уже поддерживает когерентность кэшей с помощью протокола MESI, он всегда знает какие кэш-линии были изменены другим процессором, и транзакции - это просто обёртка, дающая коду доступ к внутренностям логики кэша, которая работает независимо от того, используете вы ее явно или нет. lock-free на транзакциях будет самым оптимальным из всех возможных вариантов, если соблюдается оптимистичный доступ (транзакции пересекаются в ничтожно малом количестве случаев). Если же у вас сплошные пересечения, критическая секция чаще всего наилучший вариант (алгоритмы на CASах оптимальны лишь в крайне простых случаях, к которым деревья ИМХО не относятся). Суть транзакционной памяти: вы начинаете транзакцию, работаете с памятью как обычно, и в конце можете узнать было ли пересечение (писал ли кто-нибудь в те-же кэш линии что и вы) и откатить изменения. Если пересечений не было, оверхед полностью отсутствует. P.S. кстати, через транзакции можно сделать антиотладку. ----- PGP key | Сообщение посчитали полезным: Nimnul |
|
|
Создано: 25 декабря 2013 22:01 · Поправил: Nimnul · Личное сообщение · #8 ntldr пишет: алгоритмы на CASах оптимальны лишь в крайне простых случаях, к которым деревья ИМХО не относятся При добавлении или удалении CASов достаточно, но при повороте, нужно поменять от трех до пяти ячеек памяти атомарно, здесь и CAS не спасает, приходится вводить логику spin-wait блокировки узлов. Интересно можно ли будет обойтись без этого с помощью TSX. Если проканает я запилю дерево на чистом асме ). Хотя надежды мало. Даже если можно будет избавиться от CAS, выигрыш будет значительный, в 10 раз на каждый поток, а в целом коэффициент параллельности будет стремиться к 100%. Вобщем тему нужно сильно изучать.
----- have a nice day |
|
|
Создано: 25 декабря 2013 22:04 · Личное сообщение · #9 на ктыве есть такой популярный чел, его можно почитать на эту тему http://www.1024cores.net/ http://www.rsdn.ru/forum/info/FAQ.cpp.lock-free http://www.rsdn.ru/forum/dotnet/3721636.1 красно перекрашеное дерево обязательно что ли? бинарных деревьев для Lock free вроде бы полно в том же гугле |
|
|
Создано: 25 декабря 2013 22:23 · Личное сообщение · #10 reversecode Очереди и стеки против дерева, это как муха против слона. Сделать дерево не блокирующим еще в десять раз сложнее. Я первое дерево делал месяц в режиме одержимости. Вернее сделал я его быстро, а потом долго отлавливал баги и переписывал под разные соусы. ----- have a nice day |
|
|
Создано: 25 декабря 2013 22:55 · Личное сообщение · #11 бинарное дерево это отсортированый массив, намного проще чем левый правый узел с весом или цветом хотя конечно тебе видней что в твоем случае оптимальнее |
|
|
Создано: 25 декабря 2013 23:04 · Поправил: Nimnul · Личное сообщение · #12 reversecode Бинарное дерево это частный случай графа. И совсем не массив ). Фишка дерева в том, что элементы можно вставить или удалить в середину "массива" за разумное время. Ну а если ты хочешь использовать дерево как массив, нужно добавлять поле count в каждый узел, и тогда можно опять же за разумное время получить элемент по его индексу. Деревья не обязательно нужны для сортировки, правильнее говорить, что дерево нужно для организации элементов в неком порядке. ----- have a nice day |
|
|
Создано: 25 декабря 2013 23:24 · Поправил: reversecode · Личное сообщение · #13 бинарное дерево можно представить и ввиде масива  но я это говорил к другому, о том что возможно lock free проще реализовать в бинарном дереве(массиве) чем в красно покрашеном дереве, где проверок-блокировок больше |
|
|
Создано: 26 декабря 2013 00:22 · Личное сообщение · #14 Дерево можно хранить в структурах, а можно хранить в массиве. Но массив этот не является отсортированным в этом случае, как ты сказал постом ранее. Это так к слову. Если дерево хранится в массиве, то делать балансирующие повороты нереально за разумное время, поэтому все деревья делают в виде связанных структур. Деревья в на массиве используют чисто в академических целях, например на каких нибудь лекциях. Как я уже говорил выше, самая большая проблема в lock-free деревьях это повороты, если дерево будет в массиве то эта проблема будет еще больше, потому что для поворота там нужно будет перестраивать пол дерева. ----- have a nice day |
|
|
Создано: 26 декабря 2013 00:35 · Личное сообщение · #15 бинарное дерево является сбалансированым деревом, и если харнится в массиве то является отсортированым) но кто с тобой спорит то? я сказал выше, тебе видней для чего тебе деревья, иногда да, нужны и красно фиолетово покрашены я всего лишь подкинул мысль, что если задача впрям таки не требует всех замудренностей фиолетово разных деревьев. то можно взять и бинарное, где в реализации лок фри они будут скорее всего попроще |
|
|
Создано: 26 декабря 2013 01:58 · Поправил: Nimnul · Личное сообщение · #16 reversecode пишет: бинарное дерево является сбалансированым деревом, и если харнится в массиве то является отсортированым) Это где ты такую фигню прочитал? Вот смотри дерево:  В виде массива это дерево будет выглядеть вот так: [50, 30, 80, 20, 40, 70, 90, 0, 0, 0, 0, 60, 75, 85, 100] потому что индекс левого потомка для узла n вычисляется Ln = n * 2 + 1, а правого Rn = n * 2 + 2 reversecode пишет: то можно взять и бинарное, где в реализации лок фри они будут скорее всего попроще В том то и дело, что проще не будет, а будет вобще невозможно. Поворот узла в дереве на массиве потребует сложной перестройки ветки дерева, это само по себе будет медленно, а в lock-free и вовсе не реально. Ты прав только в случае, если избавиться от балансирующих поворотов, каким то хитрым способом. Нет поворотов нет проблем
----- have a nice day |
|
|
Создано: 31 декабря 2013 08:21 · Поправил: DrGolova · Личное сообщение · #17 > потому что индекс левого потомка для узла n вычисляется Ln = n * 2 + 1, а правого Rn = n * 2 + 2 Это свойство кучи, а не дерева. Т.е. это просто частный случай, ёба. В таком виде удобно хранить статическое дерево, но оочень неудобно модифицировать. Частичной балансировкой в данном случае будет дорогое просеивание - см. heapsort и операцию siftdown. <выпилил свои отходы мозга - идите в википедию - там подробней и понятней> |
|
|
Создано: 04 января 2014 09:40 · Личное сообщение · #18 Nimnul для того чтобы работать с бинарным деревом совсем необязательно изобретать структуру свою, а массив выглядит именно как отсортированный в одну сторону, а обход дерева происходит не за счет структуры данных, а за счет алгоритма бинарного поиска, к примеру MySql в своих индексах(В-Tree) использует бинарный поиск, и данные хранятся упорядоченно отсортированно в одну сторону. |
|
|
Создано: 08 января 2014 23:33 · Поправил: TheNozza · Личное сообщение · #19 <<Деревья не обязательно нужны для сортировки. Конечно. Ведь сортировку можно выполнять на обычном массиве. Например: Insertion Sort имеет ассимптотические верхнюю/нижнюю границы O(n^2) и Ω(n) Selection Sort - ассимптотически точная оценка Θ(n^2) Merge Sort - ассимптотически точная оценка Θ(n*log(n)) (следует из рекурентного соотношения для Merge Sort - T(n) = 2*T(n/2) + Θ(n)) |
|
|
Создано: 14 января 2014 17:00 · Поправил: Nimnul · Личное сообщение · #20 ZX-CodeR Интересно кого ты пытаешься просветить этим кэповским постом. Да я вкурсе, что в отсортированном массиве, бинарный поиск делает те же log2(n) шагов. Но вот вставка в массив потребует передвижения в среднем n / 2 элементов, а вставка в дерево log2(n) операций. Чувствуешь разницу? Сразу видно что ты деревьями никогда не занимался. TheNozza Сортировку можно делать даже на папирусе или на камне с зубилом, разница всего-ничего только во времени выполнения. DrGolova но оочень неудобно модифицировать. Если твой ответ адресован мне, то я вобще то говорю о том же самом. Читать что было написанно выше, признак хорошего тона. Нет времени читать, лучше тогда и не отвечать. Это свойство кучи, а не дерева. Это свойство двоичного представления данных, а куча там или дерево уже не имеет значения. Основное свойство кучи в том, что потомки больше родителя (или меньше). ----- have a nice day |
|
|
Создано: 17 января 2014 22:38 · Личное сообщение · #21 Nimnul C использованием дерева ты сможешь отсортировать любую последовательность лучше, чем O(n*log(n))? |
|
|
Создано: 21 января 2014 01:10 · Поправил: Nimnul · Личное сообщение · #22 TheNozza Если речь идет о классических деревьях где каждый узел содержит в себе данные. Среднее время для дерева будет O(nmin*log(nmin) + nmax*log(nmax)) / 2, поскольку nmin = 0 то получается O(n*log(n)) / 2. Есть деревья в которых данные хранятся только в листьях для них характерно O(n*log(n)). И к чему этот провокационный вопрос? ) ----- have a nice day |
|
|
Создано: 22 января 2014 23:47 · Поправил: Dr0p · Личное сообщение · #23 Nimnul Каким боком логарифмом определяется время вычислений, обьясните мне не грамотному ? Наверное процессор какой то логарифмический" ? |
|
|
Создано: 23 января 2014 05:29 · Поправил: Nimnul · Личное сообщение · #24 Dr0p Логарифм по основанию два, если отбросить не целую часть, позволяет узнать ближайший x для числа n, где n ~ 2 ^ x. Если идеально сбалансированное дерево имеет n элементов то нужно в худшем случае log2(n) шагов что бы найти в нем элемент для последующих действий над ним. ----- have a nice day | Сообщение посчитали полезным: Dr0p |
|
eXeL@B —› Программирование —› Lock-Free деревья |
Для печати