Czy Ana - / Katamorfizmy są po prostu wolniejsze?

Po napisaniu tego artykułu postanowiłem umieścić swoje pieniądze tam, gdzie są moje usta i zacząłem przekonwertować mój poprzedni projekt do użycia recursion-schemes.

Omawiana struktura danych to lazy kdtree. Proszę spojrzeć na implementacje z explicit i implicit rekurencją.

Jest to w większości prosta konwersja w następujący sposób: 

data KDTree v a = Node a (Node v a) (Node v a) | Leaf v a

Do 

data KDTreeF v a f = NodeF a f f | Leaf v a

Teraz po porównywaniu całego shebang Uważam, że wersja KDTreeF jest około dwa razy wolniejsza niż wersja normalna ( znajdź cały bieg tutaj ).

Czy to tylko dodatkowe Fix opakowanie spowalnia mnie tutaj? Czy jest coś, co mógłbym zrobić przeciwko temu?

Zastrzeżenia:

  • w tej chwili jest to wyspecjalizowane do (V3 Double).
  • to jest cata-po zastosowaniu anamorfizmu. Hylomorfizm nie jest odpowiedni dla kdtrees.
  • używam cata (fmap foo algebra) kilka razy. Czy to dobra praktyka?
  • używam pakietu Edwards recursion-schemes.

Edit 1:

Czy to ma związek? https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers Czy newtype Fix f = Fix (f (Fix f)) nie jest "wolny"?

Edit 2:

Właśnie zrobiłem kolejny zestaw testów. Tym razem przetestowałem konstrukcję i dekonstrukcję drzew. Benchmark tutaj: https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

Podczas gdy wyjście rdzenia wskazuje, że pośrednie struktury danych nie są całkowicie usuwane i nie jest zaskakujące, że liniowe wyszukiwania dominują teraz, KDTreeFS są teraz nieco szybsze niż KDTree s. nie ma to jednak większego znaczenia.

Author: Robin Green, 2014-05-15
Source

2 answers

Właśnie zaimplementowałem Thing + ThingF + Base instance wariant drzewa. I zgadnij co ... ten jest niesamowicie szybki.

Miałem wrażenie, że ten będzie najwolniejszy ze wszystkich wariantów. Naprawdę powinienem przeczytać swój własny post ... wiersz, w którym piszę:

Nie ma śladu struktury drzewa

Niech liczby mówią same za siebie, kdtreeu to nowy wariant. Wyniki nie zawsze są tak jasne, jak w tych przypadkach, ale w większości przypadków są co najmniej tak szybkie jak Jawna rekurencja (kdtree w benchmarku).

Wyniki porównawcze

 16
Author: fho,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-05-17 09:29:38

Nie używałem schematów rekursji, ale raczej mojego własnego "ręcznie zwijanego" cata, ana, Fix/unFix do generowania (list) i ewaluacji programów w małym języku w nadziei znalezienia takiego, który pasowałby do listy par (wejścia, wyjścia).

Z mojego doświadczenia wynika, że cata zoptymalizowała się lepiej niż rekurencja bezpośrednia i zwiększyła prędkość. Również IME, ana zapobiegła błędom przepełnienia stosu, które powodował mój naiwny generator, ale które sprawiły, że skupiły się na generowaniu ostatecznego lista.

Więc moja odpowiedź brzmiałaby: Nie, Nie zawsze są wolniejsze, ale nie widzę żadnych oczywistych problemów; więc mogą być po prostu wolniejsze w Twoim przypadku. Możliwe jest również, że samo Schematy rekurencyjne nie są zoptymalizowane pod kątem szybkości.

 1
Author: Boyd Stephen Smith Jr.,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-05-19 18:09:26