Lev Walkin (lionet) wrote,
Lev Walkin
lionet

Categories:

OCaml LRU

The quality of programmers is a decreasing function of the density of GOTO statements in the programs they produce."
— Edsger W. Dijkstra
Никто уже давно не пишет нигде GOTO. В нашем репозитарии их всего четыре штуки, и те — во втащенном стороннем Perl'овском коде. Но зато велосипеды похожего порядка величины изобретаются сплошь и рядом.

Внезапно стал необходим LRU кэш на OCaml'е. LRU (Least Recently Used) кэш — это такая конструкция, которая обеспечивает хранение наиболее часто использующихся данных. Если данные не используются, добавление новых записей в LRU приводит к вымыванию наименее использовавшихся данных из конца гипотетического списка, отсортированного по уменьшению частоты использования.

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

Стандартно крохотные LRU кеши можно делать на односвязных списках [{key, value}] (O(1) вставка, O(N) поиск элемента),
на двусвязных списках (O(1) вставка, O(N) поиск, чуть-чуть более GC-friendly),
на двусвязных списках + какой-то быстрой структуре для поиска (O(1) вставка, O(D) поиск, где O(D) можно традиционно для хешей считать O(1)).

Последний раз LRU я писал на C (2002-2003?), сейчас нужно было на OCaml. Задача сама по себе элементарная. Если бы не одно "но": связные списки. Писать ещё один двусвязный список в эпоху ракет, летящих к марсу, было бы совсем неоптимальным расходом времени. Если это ещё имеет какой-то смысл в качестве задачи для студентов, то писать связный список опять, тем более, на функциональном языке, вызывает неприятный рефлекс.

Когда я ещё пилил в Netli, наш VP of Engineering однажды подошёл, увидел что я ковыряю <sys/queue.h> (в приличных операционках — man 9 queue), и посетовал: "везде, куда ни придёшь, все пишут свои, глючные linked lists".

Вообще, связные списки (двусвязные в большей степени, но даже односвязные) — это удивительная структура данных. Она относится к числу может быть самых стрёмных структур данных по отношению "баги в имплементации / на сложность концепции". Накосячить в doubly linked list — проще простого. Проще чем в имплементации Google Protocol Buffers, по отношению к объёму соответствующей теории. Проще, чем написать интерпретатор лиспа на хаскеле. Этот факт заслуживает отдельной медицинско-биологической работы на тему зависимости концентрации внимания от простоты задачи.

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

Так вот, так как чего-то похожего на <sys/queue.h> в OCaml'е нет, то забив на NIH-синдром, я полез искать сразу код LRU. Думал, найду LRU — сэкономлю какой-то квант своего времени на имплементации.

Гугление на "lru ocaml" первым же своим ответом вынесло на соответствующую библиотеку Дастина Саллингса Lru.html, которую, к тому же, несколько раз рекомендовали в окамловских списках рассылки. Так как Дастин тоже живёт в Санта Кларе, стало очевидно что я должен использовать именно эту библиотеку.

Первый же тест функциональности модуля Lru с треском провалился.
[vlm@nala:~]> cat test.ml
let _ =
        let lru = Lru.create 42 in
        Lru.add lru "key" "value";
        Lru.remove lru "key";;
[vlm@nala:~]> ocamlopt -o test linkedlist.ml lru.ml test.ml && ./test
Fatal error: exception Out_of_memory
[vlm@nala:~]> 

Понятно, что проблема в lru.ml, ведь не может же быть так, чтобы косяк был в linkedlist.ml, на котором построен lru.ml? Ведь linked list, это элементарная структура данных даже на императивных языках, а уж на функциональных — и того проще! Не может же быть чтобы развесистая библиотека, развивавшаяся в течение нескольких лет и стабилизировавшаяся в районе 2004 года, имела проблему в двусвязных списках?

Или может?

Разобравшись, я отослал патч автору и позвонил ему, с целью поздравить с граблями.

linkedlist.ml.orig linkedlist.ml
@@ -126,7 +126,7 @@
        match l.l with
        None -> ()
        | Some el ->
-               if el = it then l.l <- Some el.next;
+               if el == it then l.l <- Some el.next;
                l.cnt <- l.cnt - 1;
                ()

Это как раз та ошибка, из-за которой программа валилась от Out of memory.

Вот мой квотинг и ответ Дастина:

> It turns out, the bug is not in the LRU library, but in the Linkedlist module. It used structural comparison (el = it) instead of physical comparison (el == it) and probably hit some GC-related timing issue in a newer OCaml version (I don't believe it did not ever work for you, so I presume it worked on some earlier OCaml version).

Hey, that's great. I was just getting that error in something I hadn't touched in a while and assumed for some reason that it was a bug in ocaml (since that was the only thing that changed).


То есть, компайлер сменился, и код двусвязного списка вдруг перестал работать.

В итоге, я потратил на то чтобы разобраться с проблемой и накатать этот пост больше времени, чем заняло бы создание собственной имплементации LRU. Всенепременнейше, со своими собственными багами.

[1] Evolutionary Trends of Programming Languages, 2003
[2] http://rosettacode.org/w/index.php?title=Doubly-Linked_List_(element)
Tags: ocaml
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 31 comments