Skip to contentSkip to conversation

coccinelle computes patch very slowly

Cocci Michele Martone 2 participants 8 messages Jun 25, 2018 – Jun 27, 2018 2 messages not in the archive

lore
Share & tools
lore
#0 lore raw

Dear Coccinelle Team,

While patching source files of a few thousand lines long, I noticed prohibitively long patch compute times (seemed hanged).

This effectively prevented spatch from being usable.

I attach a minimalistic program and patch replicating the problem.

It seems like presence of uninitialized variables and/or a loops body might slow down spatch computation extremely.

I will be grateful of any support!
Michele
-------------- next part --------------
/*
// A semantic patch introducing casting on function return:
@@
type T;
identifier I;
symbol f;
@@

T I;
...

-I =
+I = (T)
f(...);
*/
// Unfortunately, the above semantic patch takes 44s to run spatch --sp-file <patch above> <snippet below> !
// By using initializing declarators, or deleting the loop, it takes a fraction of a second.
// Tested with a coccinelle version 04d390a4414e626a0ca83f65f1ec08390c378cd1 (Sat May 26 07:43:36 2018 +0200).
// spatch version 1.0.6-00440-ga4532f08 compiled with OCaml version 4.08.0+dev0-2018-04-09
void * f(){return 0;}
void g(void)
{
int v1=0, v2=0;
int *a1, *a2;
int presence, of, these, slows, down, patch, computing, extremely, y1, y2, y3, y4, y5;//each new uninitialized variable can cost seconds! //int presence=0, of=0, these=0, slows=0, down=0, patch=0, computing=0, extremely=0, y1=0, y2=0, y3=0, y4=0, y5=0;//inizialized ones are fine //undefined_t status;// presence of this (if uncommented) slows down a lot
a1 = f();
for(v1 = 0; v1 < v2; v1++) { } // presence of this loop here, too! delete it to have a huge speedup ?!
a2 = f();
}

#3 lore raw
In reply to a message not in the archive
Quoted 15 lines · SF Markus Elfring
Quoted 2 lines

While patching source files of a few thousand lines long, I noticed prohibitively long patch compute times (seemed hanged).

Do you get nicer run time characteristics if you would refactor the SmPL script example like the following for the addition of a type cast?

// A semantic patch introducing casting on function return:
@@
identifier F, V;
type T;
@@
T V;
...
V =
+ (T)

Quoted 1 line
     F(...);

Hi Markus,

using your patch
(having F as any identifier, rather than a specific token) does not change anything time-wise, unfortunately :-(

p.s.: My general problem actually was more complicated than this,
in that the variables declarations can be anywhere, while this patch here requires declaration and F call to be in the same scope.

Michele

#4 lore raw
Quoted 20 lines · Michele Martone
Quoted 15 lines · SF Markus Elfring
Quoted 2 lines

While patching source files of a few thousand lines long, I noticed prohibitively long patch compute times (seemed hanged).

Do you get nicer run time characteristics if you would refactor the SmPL script example like the following for the addition of a type cast?

// A semantic patch introducing casting on function return:
@@
identifier F, V;
type T;
@@
T V;
...
V =
+ (T)

Quoted 1 line
     F(...);

Hi Markus,

Quoted 8 lines

using your patch
(having F as any identifier, rather than a specific token) does not change anything time-wise, unfortunately :-(

p.s.: My general problem actually was more complicated than this,
in that the variables declarations can be anywhere, while this patch here requires declaration and F call to be in the same scope.

The call to F can be in a nested scope.

julia

Quoted 7 lines

Michele
_______________________________________________
Cocci mailing list
Cocci at systeme.lip6.fr
https://systeme.lip6.fr/mailman/listinfo/cocci

#5 lore raw
In reply to Michele Martone
Quoted 5 lines · Michele Martone

Dear Coccinelle Team,

While patching source files of a few thousand lines long, I noticed prohibitively long patch compute times (seemed hanged).

Quoted 8 lines

This effectively prevented spatch from being usable.

I attach a minimalistic program and patch replicating the problem.

It seems like presence of uninitialized variables and/or a loops body might slow down spatch computation extremely.

I will be grateful of any support!

Loops can cause the matching process to become very expensive.

I was about to propose various solutionsto get around the loop problem, but I think you don't care. You just want to know the type of I. Hence:

@@
type T;
idexpression T I;
identifier f;
@@

I =
+ (T)
f(...)

julia

#6 lore raw
Quoted 6 lines · Julia Lawall
Quoted 5 lines · Michele Martone

Dear Coccinelle Team,

While patching source files of a few thousand lines long, I noticed prohibitively long patch compute times (seemed hanged).

Quoted 8 lines
Quoted 8 lines

This effectively prevented spatch from being usable.

I attach a minimalistic program and patch replicating the problem.

It seems like presence of uninitialized variables and/or a loops body might slow down spatch computation extremely.

I will be grateful of any support!

Hi Julia,

Quoted 1 line

Loops can cause the matching process to become very expensive.

With your suggeston below (thanks!) I was able to go around the problem (see comments) !

However, I hope that this behaviour is unintended.

I mean: to practical means, loop presence, or a growing amount of uninitialized variables leading to supra-linear patch compute times is a game-stopper: it can IMHO severely scare users... I hope it is some algorithmic limitation that can be overcome..

Quoted 2 lines

I was about to propose various solutionsto get around the loop problem, but I think you don't care.

I do care --- I am open to further techniques --- they might very likel y come in handy soon ;-).
So you may send them, please.

Quoted 11 lines

You just want to know the type of I. Hence:

@@
type T;
idexpression T I;
identifier f;
@@

I =
+ (T)
f(...)

Now the POC code gets patched in a fraction of a second. And a 1.2KLOC source with 17 occurrences of 'f' in just <1s. So my practical problem here is solved: thanks!

I have an extra question.
I observed that applying:
spatch --sp-file <patch above> <120 files totalling 140 KLOC>
seems to take >4 minutes time and consuming > 5.5 GB of memory; I reran on each file separately, concatenating the patches. Then it finishes in ~40s, computing the same exact patch.

Given such a simple patch, was this expected to be so ?

Cheers,
Michele

#7 lore raw
Quoted 23 lines · Michele Martone
Quoted 6 lines · Julia Lawall
Quoted 5 lines · Michele Martone

Dear Coccinelle Team,

While patching source files of a few thousand lines long, I noticed prohibitively long patch compute times (seemed hanged).

Quoted 8 lines
Quoted 8 lines

This effectively prevented spatch from being usable.

I attach a minimalistic program and patch replicating the problem.

It seems like presence of uninitialized variables and/or a loops body might slow down spatch computation extremely.

I will be grateful of any support!

Hi Julia,

Quoted 1 line

Loops can cause the matching process to become very expensive.

With your suggeston below (thanks!) I was able to go around the problem (see comments) !

Quoted 6 lines

However, I hope that this behaviour is unintended.

I mean: to practical means, loop presence, or a growing amount of uninitialized variables leading to supra-linear patch compute times is a game-stopper: it can IMHO severely scare users... I hope it is some algorithmic limitation that can be overcome..

It is an algorithmic limitation, but I don't think it can be overcome in general. Coccinelle follows control-flow paths. When A ... B matches a case where there is a loop between A and B, then there is an infinite loop that blocks going from A to B. The solution is to use what is called weak until (Coccinelle matching is based on computational tree logic). This inlvoves negating everything and somehow reaching the fixed point in terms of the code outside the loop, rather than the code inside the loop. This easily explodes. A solution could be --no-loops, since you don't care about situations that start at the end of a loop and jump around to the top in your case. You can also use a timeout, to get an overall result quickly at the risk of missing some results. You can also reduce the problem by having one rule that matches a declaration, and another rule that makes the transformation for each declared variable individually; currently paths for different variables are interfering with each other and further inflating the cost. You can also check whether there exists a path from the declaration to a variable use, by putting exists in the header, to be able to ignore variables that are simply never used.

Quoted 22 lines
Quoted 2 lines

I was about to propose various solutionsto get around the loop problem, but I think you don't care.

I do care --- I am open to further techniques --- they might very likel y come in handy soon ;-).
So you may send them, please.

Quoted 11 lines

You just want to know the type of I. Hence:

@@
type T;
idexpression T I;
identifier f;
@@

I =
+ (T)
f(...)

Now the POC code gets patched in a fraction of a second. And a 1.2KLOC source with 17 occurrences of 'f' in just <1s. So my practical problem here is solved: thanks!

Quoted 8 lines

I have an extra question.
I observed that applying:
spatch --sp-file <patch above> <120 files totalling 140 KLOC>
seems to take >4 minutes time and consuming > 5.5 GB of memory; I reran on each file separately, concatenating the patches. Then it finishes in ~40s, computing the same exact patch.

Given such a simple patch, was this expected to be so ?

When you put many files on the command line, it works on the all at once, in order to be able to take into account references from oneto the other. Since there are 120 of them, that will be a lot of live memory which will stress the OCaml garbage collector. When you run on the files individually the garbage collector is happy - the OCaml GC works well when it only has to collect the minor heap.

Normally, when you have many files to work on, you give the name of the enclosing directory and Coccinelle works on all of them. Then it works one file at a time. If that is not suitable for your use case, then you can make a file with the names of the files you are interested in, separated by blank lines, ad git the argument --file-groups filename. Then it will only work on the listed files, again one at a time.

julia

Quoted 4 lines

Cheers,
Michele

#8 lore raw
Quoted 40 lines · Julia Lawall
Quoted 23 lines · Michele Martone
Quoted 6 lines · Julia Lawall
Quoted 5 lines · Michele Martone

Dear Coccinelle Team,

While patching source files of a few thousand lines long, I noticed prohibitively long patch compute times (seemed hanged).

Quoted 8 lines
Quoted 8 lines

This effectively prevented spatch from being usable.

I attach a minimalistic program and patch replicating the problem.

It seems like presence of uninitialized variables and/or a loops body might slow down spatch computation extremely.

I will be grateful of any support!

Hi Julia,

Quoted 1 line

Loops can cause the matching process to become very expensive.

With your suggeston below (thanks!) I was able to go around the problem (see comments) !

Quoted 6 lines

However, I hope that this behaviour is unintended.

I mean: to practical means, loop presence, or a growing amount of uninitialized variables leading to supra-linear patch compute times is a game-stopper: it can IMHO severely scare users... I hope it is some algorithmic limitation that can be overcome..

It is an algorithmic limitation, but I don't think it can be overcome in general. Coccinelle follows control-flow paths. When A ... B matches a case where there is a loop between A and B, then there is an infinite loop that blocks going from A to B. The solution is to use what is called weak until (Coccinelle matching is based on computational tree logic). This inlvoves negating everything and somehow reaching the fixed point in terms of the code outside the loop, rather than the code inside the loop. This easily explodes. A solution could be --no-loops, since you don't care about situations that start at the end of a loop and jump around to the

Quoted 8 lines

top in your case. You can also use a timeout, to get an overall result quickly at the risk of missing some results. You can also reduce the problem by having one rule that matches a declaration, and another rule that makes the transformation for each declared variable individually; currently paths for different variables are interfering with each other and further inflating the cost. You can also check whether there exists a path from the declaration to a variable use, by putting exists in the header, to be able to ignore variables that are simply never used.

Hmmm I see, these are the innards... thanks!
But .. for what C is concerned, the presence of a loop construct between a variable declaration and its use after the loop shall not be of any problem wrt type and visibility of that variable identifier. So in principle in the future one might think to follow this logic --- at least for C --- if desired --- no ?

Quoted 29 lines
Quoted 29 lines
Quoted 2 lines

I was about to propose various solutionsto get around the loop problem, but I think you don't care.

I do care --- I am open to further techniques --- they might very likel y come in handy soon ;-).
So you may send them, please.

Quoted 11 lines

You just want to know the type of I. Hence:

@@
type T;
idexpression T I;
identifier f;
@@

I =
+ (T)
f(...)

Now the POC code gets patched in a fraction of a second. And a 1.2KLOC source with 17 occurrences of 'f' in just <1s. So my practical problem here is solved: thanks!

I have an extra question.
I observed that applying:
spatch --sp-file <patch above> <120 files totalling 140 KLOC>
seems to take >4 minutes time and consuming > 5.5 GB of memory; I reran on each file separately, concatenating the patches. Then it finishes in ~40s, computing the same exact patch.

Quoted 8 lines
Quoted 1 line

Given such a simple patch, was this expected to be so ?

When you put many files on the command line, it works on the all at once, in order to be able to take into account references from oneto the other. Since there are 120 of them, that will be a lot of live memory which will stress the OCaml garbage collector. When you run on the files individually the garbage collector is happy - the OCaml GC works well when it only has to collect the minor heap.

Ok, I see..

Quoted 6 lines

Normally, when you have many files to work on, you give the name of the enclosing directory and Coccinelle works on all of them. Then it works one file at a time. If that is not suitable for your use case, then you can make a file with the names of the files you are interested in, separated by blank lines, ad git the argument --file-groups filename. Then it will only work on the listed files, again one at a time.

Sounds like a very useful option!

I did not find it in `man spatch'.
That is a pity.

I have two suggestions for `man spatch':

1.
SYNOPSIS
spatch --sp-file <SP> <files> [-o <outfile> ] [--iso-file <iso> ] [ options ] +spatch --help
+spatch --longhelp

(otherwise --longhelp is buried in the man page and difficult to see1)

2. Keep the `man spatch' page in sync with the actual options. I'm sure for OCaml wizards like you this shall be pretty easy to do automatically ;-)

Thanks,
Michele

#9 lore raw
Quoted 49 lines · Michele Martone
Quoted 40 lines · Julia Lawall
Quoted 23 lines · Michele Martone
Quoted 6 lines · Julia Lawall
Quoted 5 lines · Michele Martone

Dear Coccinelle Team,

While patching source files of a few thousand lines long, I noticed prohibitively long patch compute times (seemed hanged).

Quoted 8 lines
Quoted 8 lines

This effectively prevented spatch from being usable.

I attach a minimalistic program and patch replicating the problem.

It seems like presence of uninitialized variables and/or a loops body might slow down spatch computation extremely.

I will be grateful of any support!

Hi Julia,

Quoted 1 line

Loops can cause the matching process to become very expensive.

With your suggeston below (thanks!) I was able to go around the problem (see comments) !

Quoted 6 lines

However, I hope that this behaviour is unintended.

I mean: to practical means, loop presence, or a growing amount of uninitialized variables leading to supra-linear patch compute times is a game-stopper: it can IMHO severely scare users... I hope it is some algorithmic limitation that can be overcome..

It is an algorithmic limitation, but I don't think it can be overcome in general. Coccinelle follows control-flow paths. When A ... B matches a case where there is a loop between A and B, then there is an infinite loop that blocks going from A to B. The solution is to use what is called weak until (Coccinelle matching is based on computational tree logic). This inlvoves negating everything and somehow reaching the fixed point in terms of the code outside the loop, rather than the code inside the loop. This easily explodes. A solution could be --no-loops, since you don't care about situations that start at the end of a loop and jump around to the

Quoted 8 lines

top in your case. You can also use a timeout, to get an overall result quickly at the risk of missing some results. You can also reduce the problem by having one rule that matches a declaration, and another rule that makes the transformation for each declared variable individually; currently paths for different variables are interfering with each other and further inflating the cost. You can also check whether there exists a path from the declaration to a variable use, by putting exists in the header, to be able to ignore variables that are simply never used.

Quoted 6 lines

Hmmm I see, these are the innards... thanks!
But .. for what C is concerned, the presence of a loop construct between a variable declaration and its use after the loop shall not be of any problem wrt type and visibility of that variable identifier. So in principle in the future one might think to follow this logic --- at least for C --- if desired --- no ?

Coccinelle is not going to have a special case for this. You are free to use the --no-loops option.

julia

Quoted 68 lines
Quoted 30 lines
Quoted 30 lines
Quoted 3 lines

I was about to propose various solutionsto get around the loop problem, but I think you don't care.

I do care --- I am open to further techniques --- they might very likel y come in handy soon ;-).
So you may send them, please.

Quoted 11 lines

You just want to know the type of I. Hence:

@@
type T;
idexpression T I;
identifier f;
@@

I =
+ (T)
f(...)

Now the POC code gets patched in a fraction of a second. And a 1.2KLOC source with 17 occurrences of 'f' in just <1s. So my practical problem here is solved: thanks!

I have an extra question.
I observed that applying:
spatch --sp-file <patch above> <120 files totalling 140 KLOC>
seems to take >4 minutes time and consuming > 5.5 GB of memory; I reran on each file separately, concatenating the patches. Then it finishes in ~40s, computing the same exact patch.

Quoted 8 lines
Quoted 1 line

Given such a simple patch, was this expected to be so ?

When you put many files on the command line, it works on the all at once, in order to be able to take into account references from oneto the other. Since there are 120 of them, that will be a lot of live memory which will stress the OCaml garbage collector. When you run on the files individually the garbage collector is happy - the OCaml GC works well when it only has to collect the minor heap.

Ok, I see..

Quoted 6 lines

Normally, when you have many files to work on, you give the name of the enclosing directory and Coccinelle works on all of them. Then it works one file at a time. If that is not suitable for your use case, then you can make a file with the names of the files you are interested in, separated by blank lines, ad git the argument --file-groups filename. Then it will only work on the listed files, again one at a time.

Sounds like a very useful option!

I did not find it in `man spatch'.
That is a pity.

I have two suggestions for `man spatch':

1.
SYNOPSIS
spatch --sp-file <SP> <files> [-o <outfile> ] [--iso-file <iso> ] [ options ] +spatch --help
+spatch --longhelp

(otherwise --longhelp is buried in the man page and difficult to see1)

2. Keep the `man spatch' page in sync with the actual options. I'm sure for OCaml wizards like you this shall be pretty easy to do automatically ;-)

Thanks,
Michele