?

Log in

No account? Create an account

Previous Entry | Next Entry

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:

Comments

( 35 comments — Leave a comment )
dmzlj
Apr. 27th, 2009 12:26 pm (UTC)
Никто уже давно не пишет нигде GOTO.

В моей имплементации VM бипа - их более 60-ти!
lionet
Apr. 27th, 2009 12:38 pm (UTC)
Ой, что бы подумал про тебя Дейкстра!

Код генерируется хотя бы? Direct threading?
(no subject) - dmzlj - Apr. 27th, 2009 12:47 pm (UTC) - Expand
nealar
Apr. 27th, 2009 12:56 pm (UTC)
Если учесть, что это экологическая ниша асма - то маловато. :)
(no subject) - dmzlj - Apr. 27th, 2009 12:58 pm (UTC) - Expand
(Deleted comment)
(no subject) - dmzlj - Apr. 27th, 2009 01:15 pm (UTC) - Expand
(no subject) - lionet - Apr. 27th, 2009 01:18 pm (UTC) - Expand
(no subject) - dmzlj - Apr. 27th, 2009 01:26 pm (UTC) - Expand
(no subject) - nealar - Apr. 27th, 2009 01:37 pm (UTC) - Expand
(no subject) - dmzlj - Apr. 27th, 2009 01:45 pm (UTC) - Expand
(no subject) - nealar - Apr. 27th, 2009 02:49 pm (UTC) - Expand
(no subject) - lionet - Apr. 27th, 2009 03:09 pm (UTC) - Expand
(no subject) - nealar - Apr. 27th, 2009 03:35 pm (UTC) - Expand
(no subject) - dmzlj - Apr. 27th, 2009 05:33 pm (UTC) - Expand
(Deleted comment)
lionet
Apr. 27th, 2009 01:14 pm (UTC)
Практика показывает, что очень даже можно. Если у тебя такого ни разу не было, значит недостаточно тестировал ;)
(Deleted comment)
(no subject) - lionet - Apr. 27th, 2009 01:20 pm (UTC) - Expand
(Deleted comment)
(no subject) - lionet - Apr. 27th, 2009 05:21 pm (UTC) - Expand
(Deleted comment)
lionet
Apr. 27th, 2009 01:17 pm (UTC)
1. В Окамле есть проблема: он нечистый. Отсюда две проблемы: a) статическая типизация у него протекает, и b) есть различие между структурным тестом и физическим тестом.

2. Двусвязные списки? Нах лисп! Рефал надо брать.
(Deleted comment)
(no subject) - thesz - Apr. 27th, 2009 09:17 pm (UTC) - Expand
(Deleted comment)
(no subject) - thesz - Apr. 28th, 2009 07:15 am (UTC) - Expand
(Deleted comment)
(no subject) - lionet - Apr. 27th, 2009 08:56 pm (UTC) - Expand
smalgin
Apr. 27th, 2009 04:58 pm (UTC)
Зато вы помогли обществу :)
thesz
Apr. 27th, 2009 09:19 pm (UTC)
LRU - это кэш.

Вот не мои несколько копеек в ответе на мой вопрос: http://thesz.livejournal.com/324222.html ;)
lionet
Apr. 27th, 2009 09:26 pm (UTC)
Ага, чистый вариант с O(logN).
avnik
Apr. 28th, 2009 10:51 am (UTC)
А Окамль еще где-то употребляется для практических задач?
lionet
Apr. 28th, 2009 10:57 am (UTC)
Да.
(Deleted comment)
(no subject) - lionet - Nov. 13th, 2009 09:46 pm (UTC) - Expand
(Deleted comment)
(Deleted comment)
Re: О, что я нашёл - lionet - May. 1st, 2009 05:36 pm (UTC) - Expand
(Deleted comment)
Re: О, что я нашёл - lionet - May. 1st, 2009 05:59 pm (UTC) - Expand
(Deleted comment)
( 35 comments — Leave a comment )

Profile

lionet
Lev Walkin
Website

Latest Month

December 2016
S M T W T F S
    123
45678910
11121314151617
18192021222324
25262728293031
Powered by LiveJournal.com
Designed by yoksel