Best ways to process massive log files with DCGs

[david-sitsky]

Hi,

I'm writing an experimental parser for very large log files to pull out salient facts using DCGs. What is the right way for achieving this that is space and time efficient? As a trivial example, if I wanted to determine how many lines were present in a log file (either with \r\n or \n) a naive implementation might look like this:

:- use_module(library(dcgs)).
:- use_module(library(pio)).

newline --> "\xd\\xa\".
newline --> "\xa\".

log_file(C0, C) -->
    ...,
    newline,
    { C1 is C0 + 1 },
    log_file(C1, C).

log_file(C, C) --> [].

Then I can call the following to get an answer from C.

?- once(phrase_from_file(log_file(0, C), '/data/test.log')).

I have found with the latest scryer on master, for a 70 meg log file (which is not considered large) this can grow the heap to many gigs and it will take quite some time before completing (but it does). Given the recursive formulation above, I can understand why.

I noticed with a similar program for SWI, I get "ERROR: Out of global stack" very quickly. However if I put in a cut (!) after newline to indicate I am not interested in any other solutions (fine for this use-case), SWI completes quickly and with constant space, I assume because it has optimised this. I don't see the same effect with scryer however.

I was hoping with DCGs there would be a nice way to express this and still realise good space/time efficiency. In my real-life example, the log format I am parsing is not trivial and each entry may involve several lines.

Is there an alternative way to handling this sort of parsing problem that will be more space/time efficient? Or are cuts with "optimisation" the only way?

[UWN]

Whenever you want to process large files start with small ones. So small, that their content fits conveniently into a single line. For this, just use phrase/2 alone:

?- phrase(log_file(0,N),"1\n2\n3\n").
   N = 3
;  N = 2, unexpected
;  N = 2, unexpected
;  N = 1, unexpected
;  false. % leftover choicepoint

So your non-terminal log_file//2 is ambiguous. Not only does it determine the number of newlines in a string but also all numbers smaller than this number.

In your definition you used the non-terminal ... //0 which means any sequence, starting with the empty sequence and including also sequences with newlines. You need to reformulate your query such that you get exactly one solution and no leftover choicepoint as above (that ; false at the end).

And did I say all numbers that are smaller? But zero is missing!

?- phrase(log_file(0,N),"nihil").
   false, unexpected.

Why? Let's reformulate this to ask: What does the content of files look like that have zero lines?

?- length(Xs,N),phrase(log_file(0,0),Xs).
   Xs = [], N = 0
;  loops.

So we find only this one, and by using the goal length we ensure that all possible lists are considered:

?- length(Xs,N).
   Xs = [], N = 0
;  Xs = [_A], N = 1
;  Xs = [_A,_B], N = 2
;  Xs = [_A,_B,_C], N = 3
;  ... .

nonnewlines --> [] | [C], {dif(C,'\n')}, nonnewlines.

newlines(N0,N) -->
   nonnewlines,
   ( {N is N0}
   | "\n",
      {N1 is N0+1},
     newlines(N1,N)
   ).

?- phrase(newlines(0,N),"1\n2\n3\n").
   N = 3
;  false.
?- phrase(newlines(0,N),"nihil").
   N = 0
;  false.
?- length(Xs,L), phrase(newlines(0,N),Xs).
   Xs = [], L = 0, N = 0
;  Xs = "\n", L = 1, N = 1
;  Xs = [_A], L = 1, N = 0, dif:dif(_A,'\n')
;  Xs = "\n\n", L = 2, N = 2
;  Xs = ['\n',_A], L = 2, N = 1, dif:dif(_A,'\n')
;  Xs = [_A,'\n'], L = 2, N = 1, dif:dif(_A,'\n')
;  Xs = [_A,_B], L = 2, N = 0, dif:dif(_A,'\n'), dif:dif(_B,'\n')
;  Xs = "\n\n\n", L = 3, N = 3
;  ... .

So this version now just finds exactly one answer for a given content. And, it also enumerates all possible contents.

But the ; false indicates that we still have some space for improvement. In an ideal implementation, this could be detected automatically. That is, there is no inherent reason why this cannot be done. But currently there is no Prolog system that does this and Scryer's priorities are on garbage collection.

Meanwhile you might be tempted to introduce a cut, but this will at the same time also disable general questions about all possible outcomes. That is, you would make this program incorrect for certain uses. Many programmers prefer this way. Some even use once/1 believing that it is better than a cut, not realizing that "once" abbreviates One Nebulous Cut Example.

To better understand the problem in nonnewlines//0, consider:

?- phrase(nonnewlines, "abc\ndef",Xs).
   Xs = "abc\ndef"
;  Xs = "bc\ndef"
;  Xs = "c\ndef"
;  Xs = "\ndef"
;  false.

This is all fine except for the ; false which indicates that one or more leftover choicepoints are created using up precious resources. Here is a better definition of nonnewlines//0 that avoids this choicepoint.

?- phrase(nonnewlines, "abc\ndef",Xs).
   Xs = "abc\ndef"
;  Xs = "bc\ndef"
;  Xs = "c\ndef"
;  Xs = "\ndef".

nonnewlines --> call(nonnewlines2).  % interface to direct definition

nonnewlines2(Cs0,Cs) :-
   nonvar(Cs0),
   !,
   (  Cs0 = [C|Cs1]
   -> (  nonvar(C)
      -> (  C == '\n'
	 -> Cs0 = Cs % leftover choicepoint avoided
	 ;  Cs0 = Cs
	 ;  nonnewlines2(Cs1,Cs)
	 )
      ;  Cs0 = Cs
      ;  dif(C,'\n'),
	 nonnewlines2(Cs1,Cs)
      )
   ;  Cs0 = Cs % leftover choicepoint avoided
   ).
nonnewlines2(Cs,Cs).
nonnewlines2([C|Cs0],Cs) :-
   dif(C,'\n'),
   nonnewlines2(Cs0,Cs).

All this complex code just to avoid leftover choicepoints in those two cases above!

Will this solve your problem? Only when there will be garbage collection in Scryer.

Another more ad hoc way to this problem is to use call_semidet/1.

(There is still one leftover choicepoint for newlines//2 but rest assured, this is precisely one just at the end so it's probably not worth optimizing)

[david-sitsky]

Many thanks for the very detailed and helpful reply! I certainly knew the naive example I posted above had lots of issues, however I was not aware of the effective methods for reducing choice-points like you have illustrated above.

It seems I'll try Scryer again once it has garbage collection.

[UWN]

There is one implementation detail I forgot to mention. In Scryer, the file content is represented in memory more compactly. Up to a factor of 24 compared to SWI. That's probably also the reason why Scryer was able to finish your test cases. On the other hand, SWI has a relatively small maximum size by default. In any case, comparisons on that level often lead to nowhere...

[UWN]

Here is a shorter version of nonnewlines2/2. Note that Prolog systems could be capable of producing this seeing just the original clean DCG rule.

nonnewlines2(Cs0,Cs) :-
   nonvar(Cs0),
   ( Cs0 = [C|_] -> C == '\n' ; true ),
   !,
   Cs0 = Cs.
nonnewlines2(Cs,Cs).
nonnewlines2([C|Cs0],Cs) :-
   dif(C,'\n'),
   nonnewlines2(Cs0,Cs).

[UWN]

Some more observations:

• The entire code up to the cut is read only. So no real unifications are happening. And thus there is no need for a choicepoint and saving argument registers. Only upon failure the current arguments need to be saved for the last clause.
• Cs0 = [C|_] isn't really unifying. And needs no instruction for the _.