Help! mem leak in c extension.
cche
I would like your comments on this extension I'm working on. It was
working as expected as I only aligned 2 sequences and printed the
result. But actually I have a memory leak when invoking the align
function repeatedly in one program. Are the tcl objects correctly
used? Actually, I'm a C newbee so any help in tracking this leak down
would be appreciated.
Thanks
cche
int
align_Cmd (
ClientData clientData, /* Not used. */
Tcl_Interp *interp, /* Current interpreter */
int objc, /* Number of arguments */
Tcl_Obj *const objv[] /* Argument strings */
)
{
char *sequence1, *sequence2;
signed int x, xmax, y, ymax, itemscore[3], best, i, t;
int at, bt, da;
char aseq1[2*MAXLEN+1], aseq2[2*MAXLEN+1];
struct s_item atable[MAXLEN][MAXLEN];
if (objc != 6) {
Tcl_WrongNumArgs (interp, 1, objv, "<seqA> <seqB> <matrix_var>
<align_var> <score_var>");
return TCL_ERROR;
}
/* *** get sequence one and two *** */
sequence1 = Tcl_GetStringFromObj(objv[1], &xmax);
sequence2 = Tcl_GetStringFromObj(objv[2], &ymax);
/* *** create alignment table *** */
atable[0][0].score=0; atable[0][0].trace = TRACE_DIA;
for (x=1; x<=xmax; x++) {
atable[x][0].score = x * INDEL;
atable[x][0].trace = TRACE_LEFT;
}
for (y=1; y<=ymax; y++) {
atable[0][y].score = y * INDEL;
atable[0][y].trace = TRACE_UP;
}
for (y=1; y<=ymax; y++) {
for (x=1; x<=xmax; x++) {
itemscore[0]=atable[x][y-1].score+INDEL;
if (sequence1[x-1]==sequence2[y-1]) {
itemscore[1]=atable[x-1][y-1].score + MATCH;
} else {
itemscore[1]=atable[x-1][y-1].score + MISMATCH;
}
itemscore[2]=atable[x-1][y].score+INDEL;
if ((itemscore[0]>=itemscore[1])&&(itemscore[0]>=itemscore[2])) {
atable[x][y].trace = TRACE_UP;
atable[x][y].score = itemscore[0];
}
if ((itemscore[1]>=itemscore[0])&&(itemscore[1]>=itemscore[2])) {
atable[x][y].trace = TRACE_DIA;
atable[x][y].score = itemscore[1];
}
if ((itemscore[2]>=itemscore[0])&&(itemscore[2]>=itemscore[1])) {
atable[x][y].trace = TRACE_LEFT;
atable[x][y].score = itemscore[2];
}
}
}
/* *** set alignment table var *** */
char *pos;
pos = ckalloc(10*sizeof(char));
for (y=0; y<=ymax; y++) {
for (x=0; x<=xmax; x++) {
sprintf(pos, "%d,%d", x, y);
Tcl_ObjSetVar2(interp, objv[3], Tcl_NewStringObj(pos, -1),
Tcl_NewIntObj(atable[x][y].score), 0);
}
}
ckfree(pos);
// *** set alignment var ***
x = xmax; y = ymax; i = 2*MAXLEN-1;
aseq1[2*MAXLEN]=0; aseq2[2*MAXLEN]=0;
do {
t = atable[x][y].trace;
if (t == TRACE_LEFT || t == TRACE_DIA) {
aseq1[i] = sequence1[x-1];
x--;
} else aseq1[i] = '-';
if (t == TRACE_UP || t == TRACE_DIA) {
aseq2[i] = sequence2[y-1];
y--;
} else aseq2[i] = '-';
i--;
} while((x>0) || (y>0));
Tcl_Obj *res[3];
res[0] = Tcl_NewStringObj(aseq1+i+1, -1);
res[1] = Tcl_NewStringObj(aseq2+i+1, -1);
Tcl_Obj *alilist = Tcl_NewListObj(2, res);
Tcl_ObjSetVar2(interp, objv[4], NULL, alilist, 0);
/* *** set score var *** */
Tcl_ObjSetVar2(interp, objv[5], NULL, Tcl_NewIntObj(atable[xmax]
[ymax].score), 0);
return TCL_OK;
}
Alexandre Ferrieux
> I would like your comments on this extension I'm working on.
> would be appreciated.
If you're a C newbee I'd strongly recommend to stay away from the Tcl-
C interface !
Instead, just wrap your new functionality into a simple, small, short-
lived executable, and start a child process with it from Tcl with
[exec]. If your process has a significant init time, you may waive the
"short-lived" constraint and instead spawn the child between pipes
[open "|..." r+]. You may still have leaks, but they will be much
easier to debug, since they'll be confined to a simple program, and
reproducible without Tcl.
Regarding your specific task of dynamic programming, I've already been
exactly there and done exactly that. Works like a charm !
-Alex
Bezoar
I only looked at this for a little while but I did notice something
that you may
want to check into. The man page for Tcl_NewListObj it says the
following:
Tcl_NewListObj and Tcl_SetListObj create a new object or modify
an
existing object to hold the objc elements of the array
referenced by
objv where each element is a pointer to a Tcl object. If objc
is less
than or equal to zero, they return an empty object. The new
object's
string representation is left invalid. The two procedures
increment
the reference counts of the elements in objc since the list
object now
refers to them. The new list object returned by
Tcl_NewListObj has
reference count zero.
The second from last sentence is key. If TCL does not free a segment
of
memory until the reference count is 0 then
you have artificially boosted the reference count of the objects
pointed to by
members of the res array to two when you create the NewListObj. You
may
need to decrement them somehow by freeing them.
Carl
Mark Janssen
@Carl, As far as I can see, the reference count of the list elements
is only one after the NewListObj call. They will be freed when the
list is freed. (Newly created Tcl_Objs have a refCount of 0)
When the list is assigned to a var also the reference count of the
list is increased to 1 (so both list and elements now have a refCount
of 1)
When the variable the list is set to is unset or changed, the refCount
of the list drops to 0 (and is thus freed) and consequently the
elements refCount drops to 0 and are thus also freed.
So I don't think that is the problem.
@cche, how are you determining that there is a memleak? Do you have a
test script?
Mark
Ralf Fassel
| /* *** set alignment table var *** */
| char *pos;
| pos = ckalloc(10*sizeof(char));
| for (y=0; y<=ymax; y++) {
| for (x=0; x<=xmax; x++) {
| sprintf(pos, "%d,%d", x, y);
| Tcl_ObjSetVar2(interp, objv[3], Tcl_NewStringObj(pos, -1),
| Tcl_NewIntObj(atable[x][y].score), 0);
| }
| }
| ckfree(pos);
Check whether it makes a difference if you apply proper refcounting on
the Tcl_NewStringObj(pos, -1) which is used as the array-element-key
here. From looking at the TCL-code for Tcl_ObjSetVar2(), it seems TCL
does no incr/decr here for the variable name objects, so the memory is
lost after the function returns.
HTH
R'
cche
wrote:
Thanks Alex,
I'm coming from exactly the direction that you are indicating, but its
speed I'm after. I need to compare 60 character strings (60 oligomer),
400.000 of them against each other in order to select those that have
more than 4 characters of difference against any of the other
oligomers. The best solution, I think, is dynamic programming and
started with a standalone c prog invoked as you suggested. This
solution will take me several days to complete all the comparisons
while the c-extension approach reduces the necessary time to something
more realistic.
So, if you have any suggestions in order to accelerate these
comparisons I will be really happy to learn about them!
Regards,
cche
Mark Janssen
Did you consider doing it all in Tcl? The performance might suprise
you (positively)
Mark
cche
Hi Bezoar and Mark,
I tried by Tcl_DecrRefCount'ing the object pointers in res, but that
freed them (and I got weird results in the list var) as Mark already
pointed out.
Mark, the memory leak is patent as the memory of the machine gets
eaten up until a message "couldn't alloc XXX bytes" appears.
I didn't get this behaviour when doing printf of the array, alignment
or score, before. Thats why I tend to look into the Tcl interface, but
I'm not 100% sure it comes from the interface.
cche
cche
Not really, I did an implementation of local alignment in pure Tcl
some time ago, and IIRC it did not compare favorably when comparing
against 'exec c-prog'/parsing. But I think the implementation wasn't
the best neither. I'll look the code up and adapt it to do global
alignment and compare the speed. Just to be fair with our beloved Tcl
which manages to surprise us all the time.
Regards,
cche
cche
> * cche <cris.chapa...@gmail.com>
Hi Ralf,
It was this piece of code that was responsible for eating up memory. I
replaced it by
char *pos;
pos = ckalloc(10*sizeof(char));
for (y=0; y<=ymax; y++) {
for (x=0; x<=xmax; x++) {
sprintf(pos, "%d,%d", x, y);
Tcl_Obj *ppos = Tcl_NewStringObj(pos, -1);
Tcl_ObjSetVar2(interp, objv[3], ppos, Tcl_NewIntObj(atable[x]
[y].score), 0);
Tcl_DecrRefCount(ppos);
}
}
ckfree(pos);
and memory usage was stable again. In the meantime I had tried with a
list which has roughly the same time of execution and no problem of
growing mem usage too.
char *pos;
pos = Tcl_Alloc(10*sizeof(char));
Tcl_Obj *arr[2];
sprintf(pos, "%d,%d", xmax, ymax);
arr[0] = Tcl_NewStringObj("#", -1);
arr[1] = Tcl_NewStringObj(pos, -1);
Tcl_Obj *arrlist = Tcl_NewListObj(2, arr);
for (y=0; y<=ymax; y++) {
for (x=0; x<=xmax; x++) {
sprintf(pos, "%d,%d", x, y);
Tcl_ListObjAppendElement(interp, arrlist, Tcl_NewStringObj(pos,
-1));
Tcl_ListObjAppendElement(interp, arrlist, Tcl_NewIntObj(atable[x]
[y].score));
}
}
Tcl_Free(pos);
Tcl_ObjSetVar2(interp, objv[3], NULL, arrlist, 0);
Thanks everybody for your help! I think extending Tcl is not difficult
at all, It's just that a nice tutorial which would point out these
gotchas would be a real help. This relates to some comments on another
thread on a new Tcl book: man pages are good and very usable once you
now what you need. But a tutorial makes a world of difference when you
are learning.
Again, Thanks a lot.
cche
miguel
> Thanks everybody for your help! I think extending Tcl is not difficult
> at all, It's just that a nice tutorial which would point out these
> gotchas would be a real help. This relates to some comments on another
> thread on a new Tcl book: man pages are good and very usable once you
> now what you need. But a tutorial makes a world of difference when you
> are learning.
May be late, but: do http://wiki.tcl.tk/14880 and
http://wiki.tcl.tk/1192 help?
Ralf Fassel
| pos = ckalloc(10*sizeof(char));
| for (y=0; y<=ymax; y++) {
| for (x=0; x<=xmax; x++) {
| sprintf(pos, "%d,%d", x, y);
Note that 10 chars is a really narrow margin for that index buffer.
It will overflow if x and y together are larger than 8 digits. Since
xmax and ymax come in as user input, I'd rather use a LARGE buffer
here, or use a TCLDstring. Is there a reason not to use a large array
here instead of alloc/free?
char pos[1024];
sprintf(pos, "%d,%d", x, y);
HTH
R'
cche
Yes! They help a lotm specially the last paragraph of the first
page... they clarify the problem I had. It's better to see it black on
white on "paper" than to infer these things from experience. It would
be nice to have the categorization included in the man pages, or a
clear explanation/section of what each function does in terms of
refcounting.
Anyway I'm keeping these pages close by ;-)
Thanks!
cche
cche
x and y are the position of the character in the string, which is
limited in my extension to MAXLEN = 100 so everything together should
not be longer than 3+3+1=7 characters. Of course I also deal with
longer sequences and I align them constantly so I should redesign my
extension to be more general. But you are right... I'm a "self taught
programming" biologist and maybe thats why I have this tendency to
code a specific solution and after a while generalize and make a
library. I have the firm intention to change this bad habit of mine
but until now I haven't had much progress. Of course Tcl is the real
culprit here as it makes all of this so easy ;-)
Anyway, thanks for the suggestion!
cche
Alexandre Ferrieux
> wrote:
>
> > If you're a C newbee I'd strongly recommend to stay away from the Tcl-
> > C interface !
>
>
> I'm coming from exactly the direction that you are indicating, but its
> speed I'm after. I need to compare 60 character strings (60 oligomer),
> 400.000 of them against each other in order to select those that have
> more than 4 characters of difference against any of the other
> oligomers. The best solution, I think, is dynamic programming and
> started with a standalone c prog invoked as you suggested. This
> solution will take me several days to complete all the comparisons
> while the c-extension approach reduces the necessary time to something
> more realistic.
Sorry, but this doesn't make sense. If your standalone C is so slow,
coupling it more tightly with a Tcl interpreter will never improve its
algorithmic complexity, nor even win a constant factor.
Tcl is just glue, you know (though of a tremendously elegant and
flexible variety).
> So, if you have any suggestions in order to accelerate these
> comparisons I will be really happy to learn about them!
I would indeed be interested to know how your standalone program is
implemented.
Bottleneck chasing is one of the few sports I'm fond of :-)
-Alex
cche
wrote:
> On Aug 27, 9:50 pm, cche <cris.chapa...@gmail.com> wrote:
>
>
>
> > On Aug 27, 7:34 pm, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
> > wrote:
>
> > > If you're a C newbee I'd strongly recommend to stay away from the Tcl-
> > > C interface !
>
> > Thanks Alex,
> > I'm coming from exactly the direction that you are indicating, but its
> > speed I'm after. I need to compare 60 character strings (60 oligomer),
> > 400.000 of them against each other in order to select those that have
> > more than 4 characters of difference against any of the other
> > oligomers. The best solution, I think, is dynamic programming and
> > started with a standalone c prog invoked as you suggested. This
> > solution will take me several days to complete all the comparisons
> > while the c-extension approach reduces the necessary time to something
> > more realistic.
>
> Sorry, but this doesn't make sense. If your standalone C is so slow,
> coupling it more tightly with a Tcl interpreter will never improve its
> algorithmic complexity, nor even win a constant factor.
> Tcl is just glue, you know (though of a tremendously elegant and
> flexible variety).
I guess I was not very clear about the fact that the standalone prog
was not mine. By standalone c prog I meant needle from the EMBOSS
package, for example. So I normally create a Tcl interface (usually
with XOTcl) which runs the prog with the appropriate arguments and get
everything back. Then some instprocs to parse and get to the specific
results and thats it. I do use the glueing capabilities of Tcl quite
often. But I guess the non specificity of the progs and specially the
parsing take a lot of time. So the idea was to write a specific
routine in c and if I'm getting back in touch with c after 8 years of
not coding it nor reading it at all (thanks Tcl), a whole new
beginning I might add (== newbee), then why not try to write a library
for Tcl using the c interface? It's working, it took a bit of time,
but it will come faster the next time... I hope!
Do you really consider the tcl c interface as non approachable for non
experienced c programmers? It didn't frighten me that much... maybe
out of ignorance??
>
> > So, if you have any suggestions in order to accelerate these
> > comparisons I will be really happy to learn about them!
>
> I would indeed be interested to know how your standalone program is
> implemented.
> Bottleneck chasing is one of the few sports I'm fond of :-)
Sorry, next time... I promise! ;-)
Cristian
Alexandre Ferrieux
> On Aug 28, 9:06 pm, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
> wrote:
>
> > coupling it more tightly with a Tcl interpreter will never improve its
> > algorithmic complexity, nor even win a constant factor.
>
> was not mine.
Indeed you weren't ;-)
> But I guess the non specificity of the progs and specially the
> parsing take a lot of time.
Then why is it that in a Tcl extension you get less parsing work than
in the standalone case ?
Tell me: you didn't spawn your standalone program once per alignment,
did you ?
If you did, then again, make it live longer and work on data fed
through stdin.
If not, I'm lost: by what magic should a given algorithm be faster
when embedded in Tcl than outside ???
> > Bottleneck chasing is one of the few sports I'm fond of :-)
>
> Sorry, next time... I promise! ;-)
How frustrating. Now what if somebody wants to use your tool in a non-
Tcl context ?
Or if some other guy asks you to publish the theory ? Imagine the
paper's title:
Subquadratic DP-matching Through The Tcl Magic Wand
Serious about it ?
-Alex
cche
wrote:
> > But I guess the non specificity of the progs and specially the
> > parsing take a lot of time.
>
> Then why is it that in a Tcl extension you get less parsing work than
> in the standalone case ?
>
To illustrate the why I'll give you a schematic output of needle:
#########
# needle
# filename
# ... lots of program parameters here
# score = XXX
########
1 acattaacg ..... 60
| || | ||
10 acagtcgcg ..... 70
... more lines of alignment
This gets thrown out to a file or stdout so I need to parse the file/
[read $fi] to extract the score and the aligned sequence. Plus I
wanted to also have access to the scoring matrix in order to
investigate alternative alignments. this feature you don't get in the
available progs.
> Tell me: you didn't spawn your standalone program once per alignment,
> did you ?
> If you did, then again, make it live longer and work on data fed
> through stdin.
> If not, I'm lost: by what magic should a given algorithm be faster
> when embedded in Tcl than outside ???
The program exits after printing its output so I think I don't have
the choice... or have I?
> How frustrating. Now what if somebody wants to use your tool in a non-
> Tcl context ?
A standalone would indeed be better in this case. And maybe a c lib
that could be wrapped with swig would be another alternative, but then
I would need to learn how to use swig...
> Or if some other guy asks you to publish the theory ? Imagine the
> paper's title:
>
> Subquadratic DP-matching Through The Tcl Magic Wand
>
> Serious about it ?
Well., the Needleman-Wunsch algorithm has been around since 1990 so it
never crossed my mind to publish anything. I just wanted an
implementation that I could use with Tcl, that was fast, where I could
reach into the intermediate results (the array) and that would make a
nice addon to my biotcl library ;-)
Having said that, I agree that I should plan a bit more before coding
(see answer to R. Fassel), look a bit more at the bigger picture...
I'm pasting a postit with "abstract your code" on my screen as we
speak!
cche
Alexandre Ferrieux
> On Aug 28, 11:58 pm, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
> wrote:
>
> > > But I guess the non specificity of the progs and specially the
> > > parsing take a lot of time.
>
> > Then why is it that in a Tcl extension you get less parsing work than
> > in the standalone case ?
>
> To illustrate the why I'll give you a schematic output of needle:
OK - this is the blackbox executable that you didn't write.
It is hopelessly limited, especially in that it does just one
alignment and exits.
But that's not the point !!!
What I was suggesting was to take the very same DP-matching routine
that you have in your Tcl extension code (your source, no external
blackbox, right ?), and write *yourself* a simple main() instead of a
Tcl extension.
This main(), of which you are in control, would:
- load parameters (confusion matrix) once
- endlessly read pairs of strings on stdin and output their
alignment
Which completely offsets the process startup (fork) and algorithm
initialization overheads.
> A standalone would indeed be better in this case. And maybe a c lib
> that could be wrapped with swig would be another alternative, but then
> I would need to learn how to use swig...
Again, once you write the simple main() above, all you have to do from
Tcl is some I/O.
No Tcl extension API, nor even automated wrapper generation like swig.
And you debug your algorithmic part by unit tests outside Tcl. Core
dumps are unambiguous.
-Alex
Cameron Laird
.
.
While this thread makes me feel very lost, I noticed some
of the same things Ralf mentioned. Please be aware that
a string of seven characters (octets, really--we'll leave
*that* issue aside for the moment) takes eight bytes in
memory, once one accounts for C's null-terminator.
Also, the ckalloc() as used here is significantly more
expensive in time, both intrinsically and in its fragmenta-
tion consequences, than the automatic array Ralf recommends.
Cameron Laird
cche <cris.c...@gmail.com> wrote:
.
.
.
>often. But I guess the non specificity of the progs and specially the
>parsing take a lot of time. So the idea was to write a specific
.
.
I have had trouble following this thread. One possibility
that occurs to me, though, is that perhaps we can show how
readily you can change even your rhetorical "I guess ..."-s
into measured quantities that serve as a surer guide to
action.
I'll be more specific: to the extent I understand this
thread,
* process-forking
* Tcl-C interface routines
* memory allocation
* algorithmic implementations in Tcl
* parsing
have all been mentioned as possible bottlenecks. You've
asked ... well, I don't understand the questions. Your goal
of improving performance will best be met, our experience
teaches us, through simple disciplines of measurement and
design.
I summarize: you're free to guess; be aware, though, that
there are alternatives.
cche
wrote:
> But that's not the point !!!
>
> What I was suggesting was to take the very same DP-matching routine
> that you have in your Tcl extension code (your source, no external
> blackbox, right ?), and write *yourself* a simple main() instead of a
> Tcl extension.
All points taken and if I get enough time this weekend I'll make the
exercise of implementing the standalone version (without the size
limit) and tcl only versions and measure speeds.
I'll keep you informed!
cche
cche
Hi cameron,
The "I guess" was just my bad english. Of course I have measured! I
measured the external "black box" program, my first c-interface
implementation returning everything (array, alignment and score) in
one string... passing variables to the function... returning the 2d
array as a tcl array or as a list. And my current implementation is
the fastest till now. It checks the number of vars passed to the
function and will return just the score, the score and alignment or
the score/alignment/matrix (as a tcl array).
The other point was Alex convincing me to use my own standalone c prog
instead of using the cinterface of Tcl, and use it with [open |...]
because, among other things, it is easier to debug, which is something
I will do as soon as I have some time (this weekend maybe).
Finally, about the question, the only question was about an object
leak that I had and was answered, the code corrected and the extension
used to compare the oligonucleotides.
I hope this clarifies everything :-)
cche
cche
> In article <1188304129.657818.72...@d55g2000hsg.googlegroups.com>,
characters long as the index would be 4+4+1=9 plus the null
terminator.
>
> Also, the ckalloc() as used here is significantly more
> expensive in time, both intrinsically and in its fragmenta-
> tion consequences, than the automatic array Ralf recommends.
have a more general implementation of the needleman-wunsch algo in
Tcl, and maybe one day release it as part of a biotcl package if I get
to clean the code and document what I have.
Cheers!
cche
Ralf Fassel
| > Note that 10 chars is a really narrow margin for that index buffer.
| > It will overflow if x and y together are larger than 8 digits. Since
| > xmax and ymax come in as user input, I'd rather use a LARGE buffer
| > here, or use a TCLDstring. Is there a reason not to use a large array
| > here instead of alloc/free?
| > char pos[1024];
| > sprintf(pos, "%d,%d", x, y);
|
| limited in my extension to MAXLEN = 100 so everything together should
| not be longer than 3+3+1=7 characters.
I can't get at the original article with the complete code right now
(my newsserver says its no longer available?), so I can't check. But
I had the impression that there were no size limits applied to the
values converted from the objv[] for x and y. I may be wrong.
Rule of thumb: before using malloc/free, consider not using it.
R'
Cameron Laird
>measured the external "black box" program, my first c-interface
>implementation returning everything (array, alignment and score) in
>one string... passing variables to the function... returning the 2d
>array as a tcl array or as a list. And my current implementation is
>the fastest till now. It checks the number of vars passed to the
>function and will return just the score, the score and alignment or
>the score/alignment/matrix (as a tcl array).
>The other point was Alex convincing me to use my own standalone c prog
>instead of using the cinterface of Tcl, and use it with [open |...]
>because, among other things, it is easier to debug, which is something
>I will do as soon as I have some time (this weekend maybe).
>Finally, about the question, the only question was about an object
>leak that I had and was answered, the code corrected and the extension
>used to compare the oligonucleotides.
>I hope this clarifies everything :-)
>cche
>
Great! I think ... Do you have what *you* need of this encounter?
Do any bottlenecks remain that constrain your satisfaction?
Alex is absolutely right to emphasize the aptness of architecture
in terms of stand-alone processes. That's a good thing to talk about.
Good luck.
Ralf Fassel
| x and y are the position of the character in the string, which is
| limited in my extension to MAXLEN = 100 so everything together
| should not be longer than 3+3+1=7 characters.
This assumption is not correct. In your original code you had:
sequence1 = Tcl_GetStringFromObj(objv[1], &xmax);
sequence2 = Tcl_GetStringFromObj(objv[2], &ymax);
/* *** create alignment table *** */
atable[0][0].score=0; atable[0][0].trace = TRACE_DIA;
for (x=1; x<=xmax; x++) {
atable[x][0].score = x * INDEL;
atable[x][0].trace = TRACE_LEFT;
}
Note that there is no check whether the xmax/ymax values as read from
user input are indeed > 0 and < MAXLEN.
If the user specifies a really long sequence (>=MAXLEN chars), your
program will crash. http://en.wikipedia.org/wiki/Murphy%27s_law
R'
cche
Yep! it got "pasted out" in some version... it's back in together with
your pos[] suggestion! It didn't make a lot of difference speed wise,
but it sure is much safer now ;-)
Thanks!
cche
cche
(Third test, google is not playing nice with me)
I didn't have the time to do everything I wanted, but I have a pure
tcl, c-extension and external prog. The latter is the same as the c-
extension with a main, while(1), fgets and printf/fflush at the end. I
tested them with the following script:
set a "attacgcttcgactgcaactcgcacgctacgcatcgcgatcagcgctcagagactctagcg"
set b "attaccttcgagtgcaactcgcacgctatgcatcgcgatcagcgcacagagactctagcgt"
puts "Pure Tcl version:"
source ./nw.tcl
puts [time {set res [nw::align $a $b]} 100]
puts "align:\n[lindex $res 0]\n[lindex $res 1]"
puts "score: [lindex $res 2]"
puts ""
puts "tcl c-extension:"
load ./nw.so
package require nw
set ali ""
set score ""
puts [time "nw::align $a $b score ali" 100]
puts "[join $ali "\n"]"
puts "score $score"
puts ""
puts "external prog with pipe:"
set fi [open "|./cnw" r+]
puts [time {
puts $fi $a;flush $fi;puts $fi $b;flush $fi;set data [gets $fi]
} 100]
puts [join $data "\n"]
result:
$ ./t
Pure Tcl version:
57313.03 microseconds per iteration
align:
attacgcttcgactgcaactcgcacgctacgcatcgcgatcagcgctcagagactctagcg-
attac-cttcgagtgcaactcgcacgctatgcatcgcgatcagcgcacagagactctagcgt
score: 109
tcl c-extension:
84.99 microseconds per iteration
attacgcttcgactgcaactcgcacgctacgcatcgcgatcagcgctcagagactctagcg-
attac-cttcgagtgcaactcgcacgctatgcatcgcgatcagcgcacagagactctagcgt
score 109
external prog with pipe:
268.03 microseconds per iteration
attacgcttcgactgcaactcgcacgctacgcatcgcgatcagcgctcagagactctagcg-
attac-cttcgagtgcaactcgcacgctatgcatcgcgatcagcgcacagagactctagcgt
109
So for my specific problem, the c-extension was a better solution.
Nevertheless I keep in mind the fact that an external prog can be used
elsewhere and in other, non-tcl environments. Still to do: eliminate
the size restriction and optimize speed if possible. And there are
other implementations of the same global alignment algorithm that are
faster or more memory efficient, but that will be another weekend
project!
Thanks to everybody for your help and comments!
cche
Alexandre Ferrieux
>
> tcl c-extension:
> 84.99 microseconds per iteration
>
> 268.03 microseconds per iteration
>
> Nevertheless I keep in mind the fact that an external prog can be used
> elsewhere and in other, non-tcl environments.
First, you may want to replace
puts $fi $a;flush $fi;puts $fi $b;flush $fi
with
puts $fi $a\n$b
after doing once
fconfigure $fi -buffering line
Moreover, please bear in mind that in a realistic setup you'll want to
compute the alignments of thousands of different pairs of strings, in
a bulk fashion, not waiting for one result before sending the other:
set ff [open inputfile w]
foreach {x y} $hugelist {
puts $ff $x\n$y
}
flush $ff
close $ff
time {exec ./cnw < inputfile > outputfile 2>@ stderr}
set ff [open outputfile r]
while {[gets $ff result]} {use $result}
And if you arrange for your data to be fed to the app in a format
close (or identical) to that of "inputfile" above (using e.g sed, awk,
and/or paste), then you can forget the [foreach] above of course. Same
on the output side, e.g. by thresholding above a given score with awk.
*Then* you'll get a huge speed bonus, for the whole realistic dataset,
over the approach "Tcl extension + Tcl-level iteration".
-Alex
PS: I do love Tcl, but am not blinded enough by it to champion it
regardless of the conditions ;-)
cche
wrote:
> First, you may want to replace
> puts $fi $a;flush $fi;puts $fi $b;flush $fi
> with
> puts $fi $a\n$b
> after doing once
> fconfigure $fi -buffering line
309.81 usec/iter.
>
> Moreover, please bear in mind that in a realistic setup you'll want to
> compute the alignments of thousands of different pairs of strings, in
> a bulk fashion, not waiting for one result before sending the other:
<snip>
neat speed up solution...
</snip>
In this case, I extract a sequence from a genome, and for this
sequence I select 60mers that need to comply with a certain GC
content, melting temperature and number of cycles needed to synthesize
it. After this I check if the sequence is unique. I continue picking
60mers, moving along the seq in 10 character steps, until I get one
that will uniquely represent this sequence. As the alignment of the
60mers is the bottleneck in this case I didn't want to generate all
possible 60mers and then clean them out. Instead, I reduce the
alignments by breaking out of the comparison once I get the unique
sequence.
But I can see situations where I could profit from these tips...
> PS: I do love Tcl, but am not blinded enough by it to champion it
> regardless of the conditions ;-)
I guess I _am_ blindly in love with Tcl, I would have never looked at/
thought of using sed or awk to process the data. I do everything in
Tcl now! I even need to look at the man pages for these programs
whenever I'm doing something a little bit more complicated than sed -e
's/this/that/'.
Well Alex, you've got me wondering about the non-Tcl world out
there... of course I get to do some bash, perl, html/javascript and a
bit of ruby from time to time, but I always come back to the cozy
feeling of Tcl. Will I ever be able to outgrow Tcl? ;-)
Cheers!
Cristian