[Ffmpeg-devel] [PATCH] optimize ff_eval
Oded Shimon
ods15
Fri Oct 27 12:25:06 CEST 2006
On Thu, Oct 26, 2006 at 10:25:23PM +0200, Michael Niedermayer wrote:
> Hi
>
> On Thu, Oct 26, 2006 at 08:45:02PM +0200, Oded Shimon wrote:
> > I took the liberty of optimizing ff_eval for multiple runs by seperating
> > the parsing/compiling and runtime steps.
> >
> > before:
> > 97730 dezicycles in ff_eval, 1023 runs, 1 skips
> > after:
> > 13643 dezicycles in ff_parse, 1023 runs, 1 skips
>
> great :)
> what about the eval.o size?
old: -rw------- 1 ods15 ods15 70604 Oct 27 12:13 eval.o
new: -rw------- 1 ods15 ods15 73900 Oct 27 12:13 eval.o
both:-rw------- 1 ods15 ods15 82088 Oct 27 12:13 eval.o
> > What should I do with this? Deperecate or keep old ff_eval? update current
> > calls for ff_eval to this new thing?
>
> hmm, id say deprecate "now" and remove with the next major version increase
> and update all in a seperate patch as soon as this is cleaned up reviewed and
> commited
Thing is, current version is ~3 times faster for one-shot evals, not to
mention simpler API and no mallocs. I think AVOption uses eval in one-shot
cases? Might be a good idea to keep both, it would involve some inevitable
duplicate code though...
> > + double (*func0)(double);
> > + double (*func1)(void *, double);
> > + double (*func2)(void *, double, double);
>
> IMHO union or void*
fixed
> > + expr_t * param[2];
> > +};
> > +
> > +static double evalsquish( double d ) { return 1/(1+exp(4*d)); }
> > +static double evalgauss ( double d ) { return exp(-d*d/2)/sqrt(2*M_PI); }
> > +static double evalmod (void * a, double d, double d2) { return d - floor(d/d2)*d2; }
> > +static double evalmax (void * a, double d, double d2) { return d > d2 ? d : d2; }
> > +static double evalmin (void * a, double d, double d2) { return d < d2 ? d : d2; }
> > +static double evalgt (void * a, double d, double d2) { return d > d2 ? 1.0 : 0.0; }
> > +static double evalgte (void * a, double d, double d2) { return d >= d2 ? 1.0 : 0.0; }
> > +static double evaleq (void * a, double d, double d2) { return d == d2 ? 1.0 : 0.0; }
> > +static double evalpow (void * a, double d, double d2) { return pow(d, d2); }
> > +static double evalmul (void * a, double d, double d2) { return d * d2; }
> > +static double evaldiv (void * a, double d, double d2) { return d / d2; }
> > +static double evaladd (void * a, double d, double d2) { return d + d2; }
> > +
> > +static double eval_expr(Parser * p, expr_t * e) {
> > + if (e->type == 0) return e->value;
> > + else switch(e->type) {
> > + case 1: return e->value * p->const_value[e->const_index];
> > + case 2: return e->value * e->func0(eval_expr(p, e->param[0]));
> > + case 3: return e->value * e->func1(p->opaque, eval_expr(p, e->param[0]));
> > + case 4: return e->value * e->func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1]));
> > + default: assert(0); return 0;
> > + }
> > +}
>
> now while this looks nice, i think it isnt optimal, what about putting all
> the "non user" functions in the switch/case? i think it might be faster
> if not then iam fine with the above
yes, it's about 10% faster, fixed...
> > +static expr_t * parse_expr(Parser *p);
> > +
> > +static expr_t * parse_primary(Parser *p) {
> > + expr_t * d = calloc(1, sizeof(expr_t));
>
> av_malloc()/av_free()
fixed before you sent this mail :)
This new (cleaned up) patch only adds the new eval method..
- ods15
-------------- next part --------------
Index: libavcodec/eval.c
===================================================================
--- libavcodec/eval.c (revision 6797)
+++ libavcodec/eval.c (working copy)
@@ -30,6 +30,7 @@
#include "avcodec.h"
#include "mpegvideo.h"
+#include "eval.h"
#include <stdio.h>
#include <stdlib.h>
@@ -286,6 +287,259 @@
}
#endif
+struct ff_expr_s {
+ int type;
+ double value; // is sign in other types
+ union {
+ int const_index;
+ double (*func0)(double);
+ double (*func1)(void *, double);
+ double (*func2)(void *, double, double);
+ } a;
+ AVEvalExpr * param[2];
+};
+
+static double eval_expr(Parser * p, AVEvalExpr * e) {
+ switch (e->type) {
+ case 0: return e->value;
+ case 1: return e->value * p->const_value[e->a.const_index];
+ case 2: return e->value * e->a.func0(eval_expr(p, e->param[0]));
+ case 3: return e->value * e->a.func1(p->opaque, eval_expr(p, e->param[0]));
+ case 4: return e->value * e->a.func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1]));
+ case 5: return 1/(1+exp(4*eval_expr(p, e->param[0])));
+ case 6: { double d = eval_expr(p, e->param[0]); return exp(-d*d/2)/sqrt(2*M_PI); }
+ default: {
+ double d = eval_expr(p, e->param[0]);
+ double d2 = eval_expr(p, e->param[1]);
+ switch (e->type) {
+ case 7: return e->value * (d - floor(d/d2)*d2);
+ case 8: return e->value * (d > d2 ? d : d2);
+ case 9: return e->value * (d < d2 ? d : d2);
+ case 10: return e->value * (d == d2 ? 1.0 : 0.0);
+ case 11: return e->value * (d > d2 ? 1.0 : 0.0);
+ case 12: return e->value * (d >= d2 ? 1.0 : 0.0);
+ case 13: return e->value * pow(d, d2);
+ case 14: return e->value * (d * d2);
+ case 15: return e->value * (d / d2);
+ case 16: return e->value * (d + d2);
+ }
+ }
+ }
+ return NAN;
+}
+
+static AVEvalExpr * parse_expr(Parser *p);
+
+static AVEvalExpr * parse_primary(Parser *p) {
+ AVEvalExpr * d = av_mallocz(sizeof(AVEvalExpr));
+ char *next= p->s;
+ int i;
+
+ /* number */
+ d->value = av_strtod(p->s, &next);
+ if(next != p->s){
+ d->type = 0;
+ p->s= next;
+ return d;
+ }
+ d->value = 1;
+
+ /* named constants */
+ for(i=0; p->const_name && p->const_name[i]; i++){
+ if(strmatch(p->s, p->const_name[i])){
+ p->s+= strlen(p->const_name[i]);
+ d->type = 1;
+ d->a.const_index = i;
+ return d;
+ }
+ }
+
+ p->s= strchr(p->s, '(');
+ if(p->s==NULL){
+ *p->error = "missing (";
+ p->s= next;
+ return NULL;
+ }
+ p->s++; // "("
+ if (*next == '(') { // special case do-nothing
+ av_freep(&d);
+ d = parse_expr(p);
+ if(p->s[0] != ')'){
+ *p->error = "missing )";
+ return NULL;
+ }
+ p->s++; // ")"
+ return d;
+ }
+ d->param[0] = parse_expr(p);
+ if(p->s[0]== ','){
+ p->s++; // ","
+ d->param[1] = parse_expr(p);
+ }
+ if(p->s[0] != ')'){
+ *p->error = "missing )";
+ return NULL;
+ }
+ p->s++; // ")"
+
+ d->type = 2;
+ if( strmatch(next, "sinh" ) ) d->a.func0 = sinh;
+ else if( strmatch(next, "cosh" ) ) d->a.func0 = cosh;
+ else if( strmatch(next, "tanh" ) ) d->a.func0 = tanh;
+ else if( strmatch(next, "sin" ) ) d->a.func0 = sin;
+ else if( strmatch(next, "cos" ) ) d->a.func0 = cos;
+ else if( strmatch(next, "tan" ) ) d->a.func0 = tan;
+ else if( strmatch(next, "atan" ) ) d->a.func0 = atan;
+ else if( strmatch(next, "asin" ) ) d->a.func0 = asin;
+ else if( strmatch(next, "acos" ) ) d->a.func0 = acos;
+ else if( strmatch(next, "exp" ) ) d->a.func0 = exp;
+ else if( strmatch(next, "log" ) ) d->a.func0 = log;
+ else if( strmatch(next, "abs" ) ) d->a.func0 = fabs;
+ else if( strmatch(next, "squish") ) d->type = 5;
+ else if( strmatch(next, "gauss" ) ) d->type = 6;
+ else if( strmatch(next, "mod" ) ) d->type = 7;
+ else if( strmatch(next, "max" ) ) d->type = 8;
+ else if( strmatch(next, "min" ) ) d->type = 9;
+ else if( strmatch(next, "eq" ) ) d->type = 10;
+ else if( strmatch(next, "gt" ) ) d->type = 11;
+ else if( strmatch(next, "gte" ) ) d->type = 12;
+ else if( strmatch(next, "lt" ) ) { AVEvalExpr * tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = 12; }
+ else if( strmatch(next, "lte" ) ) { AVEvalExpr * tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = 11; }
+ else {
+ for(i=0; p->func1_name && p->func1_name[i]; i++){
+ if(strmatch(next, p->func1_name[i])){
+ d->a.func1 = p->func1[i];
+ d->type = 3;
+ return d;
+ }
+ }
+
+ for(i=0; p->func2_name && p->func2_name[i]; i++){
+ if(strmatch(next, p->func2_name[i])){
+ d->a.func2 = p->func2[i];
+ d->type = 4;
+ return d;
+ }
+ }
+
+ *p->error = "unknown function";
+ return NULL;
+ }
+
+ return d;
+}
+
+static AVEvalExpr * parse_pow(Parser *p, int *sign){
+ *sign= (*p->s == '+') - (*p->s == '-');
+ p->s += *sign&1;
+ return parse_primary(p);
+}
+
+static AVEvalExpr * parse_factor(Parser *p){
+ int sign, sign2;
+ AVEvalExpr * e = parse_pow(p, &sign);
+ while(p->s[0]=='^'){
+ AVEvalExpr * tmp = av_mallocz(sizeof(AVEvalExpr));
+
+ p->s++;
+
+ tmp->type = 13;
+ tmp->value = 1.;
+ tmp->param[0] = e;
+ tmp->param[1] = parse_pow(p, &sign2);
+ if (tmp->param[1]) tmp->param[1]->value *= (sign2|1);
+ e = tmp;
+ }
+ e->value *= (sign|1);
+ return e;
+}
+
+static AVEvalExpr * parse_term(Parser *p){
+ AVEvalExpr * e = parse_factor(p);
+ while(p->s[0]=='*' || p->s[0]=='/'){
+ AVEvalExpr * tmp = av_mallocz(sizeof(AVEvalExpr));
+ if(*p->s++ == '*') tmp->type = 14;
+ else tmp->type = 15;
+ tmp->value = 1.;
+ tmp->param[0] = e;
+ tmp->param[1] = parse_factor(p);
+ e = tmp;
+ }
+ return e;
+}
+
+static AVEvalExpr * parse_expr(Parser *p) {
+ AVEvalExpr * e;
+
+ if(p->stack_index <= 0) //protect against stack overflows
+ return NULL;
+ p->stack_index--;
+
+ e = parse_term(p);
+
+ while(*p->s == '+' || *p->s == '-') {
+ AVEvalExpr * tmp = av_mallocz(sizeof(AVEvalExpr));
+ tmp->type = 16;
+ tmp->value = 1.;
+ tmp->param[0] = e;
+ tmp->param[1] = parse_term(p);
+ e = tmp;
+ };
+
+ p->stack_index++;
+
+ return e;
+}
+
+static int verify_expr(AVEvalExpr * e) {
+ if (!e) return 0;
+ switch (e->type) {
+ case 2:
+ case 3: return verify_expr(e->param[0]);
+ case 4: return verify_expr(e->param[0]) && verify_expr(e->param[1]);
+ }
+ return 1;
+}
+
+void ff_eval_free(AVEvalExpr * e) {
+ if (!e) return;
+ ff_eval_free(e->param[0]);
+ ff_eval_free(e->param[1]);
+ av_freep(&e);
+}
+
+AVEvalExpr * ff_parse(char *s, const char **const_name,
+ double (**func1)(void *, double), const char **func1_name,
+ double (**func2)(void *, double, double), char **func2_name,
+ char **error){
+ Parser p;
+ AVEvalExpr * e;
+
+ p.stack_index=100;
+ p.s= s;
+ p.const_name = const_name;
+ p.func1 = func1;
+ p.func1_name = func1_name;
+ p.func2 = func2;
+ p.func2_name = func2_name;
+ p.error= error;
+
+ e = parse_expr(&p);
+ if (!verify_expr(e)) {
+ ff_eval_free(e);
+ return NULL;
+ }
+ return e;
+}
+
+double ff_parse_eval(AVEvalExpr * e, double *const_value, void *opaque) {
+ Parser p;
+
+ p.const_value= const_value;
+ p.opaque = opaque;
+ return eval_expr(&p, e);
+}
+
#ifdef TEST
#undef printf
static double const_values[]={
Index: libavcodec/eval.h
===================================================================
--- libavcodec/eval.h (revision 6797)
+++ libavcodec/eval.h (working copy)
@@ -39,4 +39,12 @@
double (**func2)(void *, double, double), char **func2_name,
void *opaque, char **error);
+typedef struct ff_expr_s AVEvalExpr;
+AVEvalExpr * ff_parse(char *s, const char **const_name,
+ double (**func1)(void *, double), const char **func1_name,
+ double (**func2)(void *, double, double), char **func2_name,
+ char **error);
+double ff_parse_eval(AVEvalExpr * e, double *const_value, void *opaque);
+void ff_eval_free(AVEvalExpr * e);
+
#endif /* AVCODEC_EVAL_H */
More information about the ffmpeg-devel
mailing list