XOR list

[stas]

Прочел об интересном трюке - хранении указателей для двусвязного списка с помощью XOR. Практичность этого трюка сомнительна, разве что в embedded, я бы сам никогда, наверное, не стал им пользоваться. Но идея красивая. 

Comments

[gns-ua.livejournal.com]

Красиво. Только по нынешним временам это должен быть какой-то очень-очень жёсткий ембеддед.

В обычный эмбед запросто суют джава/дотнет CPU.

[meshulash.livejournal.com]

Забавно.

[ygam.livejournal.com]

Мне об этом трюке рассказали лет 15 назад. Сборщик мусора должен быть в восторге от таких указателей.

[akovalenko.livejournal.com]

Я об этом трюке регулярно читаю, когда обсуждается, на чём могут обломаться сборщики мусора наподобие Boehm GC. А в жизни встречать не приходилось :)

[stas]

А есть языки, в которых есть встроеные сборщики мусора и можно делать XOR указателям? Если так, то у этих сборщиков вообще жизнь суровая и трудная.

[ygam.livejournal.com]

Сильно сомневаюсь в том, что есть такие языки.

[stas]

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

[akovalenko.livejournal.com]

На самом деле boehm gc неплохо работает в средах, где используется изрядное количество библиотек общего назначения, написанных без расчёта на GC. То есть вольности такого рода изрядно редки. Например, про трюк с int* oneBasedArray = malloc(sz)-1; я читал в связи с мусорными проблемами несколько раз, но в жизни опять же не видел.

Это мне напоминает задачу, с которой я недавно развлекался — разодрать DLL-ку на сегменты кода и данных, чтобы их можно было линковать по отдельности. Делается это исходя из того, в какой сегмент «приземляется» base relocation; теоретически никто не обещал, что такое сработает, и руками довольно легко этот метод обломать. Тем не менее, на существующих в дикой природе DLL проблем не возникает.

[akovalenko.livejournal.com]

В D можно и указатели туда-сюда кастовать, и сборщик мусора есть. Правда, учитывать такие указатели тамошний GC и не умеет, и не обещает (что естественно).

вдогонку

[akovalenko.livejournal.com]

s/сегмент/секция/, конечно же.

[ygam.livejournal.com]

Ну, так в сиплюсплюсе тоже есть Boehm garbage collector, но в отличие от сборщиков мусора в сильно типизированных языках вроде джавы, его можно обмануть, если очень постараться.

[stas]

int* oneBasedArray = malloc(sz)-1 - за такое надо руки выдергивать :) Его ж потом освободить нормально невозможно, если не помнить везде, что с ним сделали. Но код, который арифметически вычисляет указатели из набора чисел у меня есть. Правда, memory management там не очень нужен.