Geek Answers Handbook

Erlang: erl shell freezes after creating a large data structure

As suggested in the answers to the previous question , I tried to use Erlang proplistto implement the trie prefix.

The code seems to work decently ... But for some reason, it doesn't work very well with the interactive shell. When I try to start it, the shell freezes:

> Trie = trie: from_dict (). % Creates a trie from a dictionary
% ... the trie is printed ...
% Then nothing happens

I see that the new text is printed on the screen (i.e. the call is called trie:from_dict()), then the shell just hangs. Nothing new >appears, but ^gdoes nothing (but ^cultimately disables it).

With a very small dictionary (the first 50 lines /usr/share/dict/words), the hang lasts only a second or two (and the trie is created almost instantly) ... But it seems to grow exponentially with the size of the dictionary (100 words takes 5 or 10 seconds, I had no patience to try more detailed dictionaries). In addition, when the shell hangs, I notice that the process beam.smpbegins to accumulate a lot of memory (somewhere between 1 and 2 concerts).

So, is there something obvious that can cause this shell to freeze and memory usage to be incredible?

Some different comments:

  • I have a suspicion that the garbage collector is to blame, but I do not know how to profile or create an experiment to verify this.

  • I tried profiling using eprof, and nothing obvious came up.

  • Here is my add string to trie function:

add([], Trie) ->
    [ stop | Trie ];

add([Ch|Rest], Trie) ->
    SubTrie = proplists:get_value(Ch, Trie, []),
    NewSubTrie = add(Rest, SubTrie),
    NewTrie = [ { Ch, NewSubTrie } | Trie ],
    % Arbitrarily decide to compress key/value list once it gets
    % more than 60 pairs.
    if length(NewTrie) > 60 ->
            proplists:compact(NewTrie);
        true ->
            NewTrie
    end.
+2
2

( ? - . ), {Ch, NewSubTrie} Tries, , Ch .

NewTrie = [ { Ch, NewSubTrie } | Trie ]

- :

NewTrie = lists:keystore(Ch, 1, Trie, {Ch, NewSubTrie})
+3

. - , . ( ).

, . .
(: , ( ), )

, erlang (, -), , , , . , , .

, , :

1> c(trie).
{ok,trie}
2>  trie:get("ab",trie:set("aa",bar,trie:new("ab",foo))). 
foo
3> trie:get("abc",trie:set("aa",bar,trie:new("ab",foo))).
undefined
4>

code ( ): note2:

-module(trie).
-compile(export_all).
-define(NEW,{ %% 26 pairs, to avoid cost of calculating a new level at runtime
 {undefined,nodepth},{undefined,nodepth},{undefined,nodepth},{undefined,nodepth},
 {undefined,nodepth},{undefined,nodepth},{undefined,nodepth},{undefined,nodepth},
 {undefined,nodepth},{undefined,nodepth},{undefined,nodepth},{undefined,nodepth},
 {undefined,nodepth},{undefined,nodepth},{undefined,nodepth},{undefined,nodepth},
 {undefined,nodepth},{undefined,nodepth},{undefined,nodepth},{undefined,nodepth},
 {undefined,nodepth},{undefined,nodepth},{undefined,nodepth},{undefined,nodepth},
 {undefined,nodepth},{undefined,nodepth}
 }
).
-define(POS(Ch), Ch - $a + 1).

new(Key,V) -> set(Key,V,?NEW).

set([H],V,Trie) -> 
 Pos = ?POS(H),
 {_,SubTrie} = element(Pos,Trie),
 setelement(Pos,Trie,{V,SubTrie});

set([H|T],V,Trie) ->
 Pos = ?POS(H),
 {SubKey,SubTrie} = element(Pos,Trie),
 case SubTrie of
  nodepth -> setelement(Pos,Trie,{SubKey,set(T,V,?NEW)});
  SubTrie -> setelement(Pos,Trie,{SubKey,set(T,V,SubTrie)})
 end.

get([H],Trie) -> 
 {Val,_} = element(?POS(H),Trie),
 Val;
get([H|T],Trie) ->
 case element(?POS(H),Trie) of
  {_,nodepth} -> undefined;
  {_,SubTrie} -> get(T,SubTrie)
 end.
+2

More articles: