2

I compared two versions of loop in emacs and in C. Emacs byte-compiled version gives 4.5 seconds, C version gives 0.22 seconds. Why so slow? How to optimize it?

Emacs version:

;; -*- lexical-binding: t -*-

(defun test-me ()
  (let ((i 0) (j 0) (t1 (float-time)))
    (while (< i 100000000)
      (setq j (* i 7))
      (setq i (+ i 1)))
    (- (float-time) t1)))

C version:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int main(int argc, char **argv) {
    int i = 0;
    int j = 0;

    clock_t start = clock();
    while(i < 100000000) {
        j = i * 7;
        i = i + 1;
    }

    clock_t end = clock();
    float seconds = (float)(end - start) / CLOCKS_PER_SEC;
    printf("%f\n", seconds);

    return 0;
}
  • 7
    I wouldn't expect elisp to approach compiled C for speed. The speed difference here is comparable to what you might expect for Python or Perl vs C. There may be tricks to speed things up, but for number-crunching loops I wouldn't expect to get much better than this. – Tyler Jul 4 '16 at 13:52
  • 1
    Funnily enough, the Python equivalent is slower than the elisp version here. The Ruby equivalent however is a good deal faster. – wasamasa Jul 4 '16 at 14:14
  • Did any garbage collection happen? That can slow things down. Also note that the results of those computations are probably wrong because Emacs integers are limited – YoungFrog Jul 4 '16 at 15:43
  • 1
    PS. It could be that speed difference is caused by control structures, not multiplication itself. AFAIK, Python uses very optimized long-math library to do arithmetic, so it's unlikely to be slower than naive C in this regard. – wvxvw Jul 4 '16 at 16:34
  • 4
    I'm actually impressed that Elisp is only 20 times as slow as C in this test. – Stefan Jul 4 '16 at 22:20
1

Emacs Lisp is not a natively compiled language, it compiles to a portable bytecode that is interpreted. What is more, Emacs' bytecode is not the fastest bytecode ever designed. In particular, access to lexical variables is probably not as fast as it should be, and your code relies greatly on those. As mentioned by Stefan, it is surprising that your code is only 20 times slower in Emacs Lisp than in C.

Historically, There was little incentive to optimise the bytecode further, since Emacs was mostly used for editing text, and Emacs buffers are highly optimised. Since nowadays a lot of people use Emacs with Gnus, Eww, or Wanderlust, we're waiting with held breath for the hero who will spend a year or two of their life reimplementing the Emacs Lisp runtime in a better way.

1

What is Emacs doing in code? Here is my analysis:

The bytecode of elisp code doing the loop:

0       constant  0
1       dup       
2       constant  float-time
3       call      0
4:1     stack-ref 2
5       constant  100000000
6       lss       
7       goto-if-nil 2
10      stack-ref 2
11      constant  7
12      mult      
13      stack-set 2
15      stack-ref 2
16      add1      
17      stack-set 3
19      goto      1
22:2    constant  float-time
23      call      0
24      stack-ref 1
25      diff      
26      return  

Opcode "mult" is defined as case expression in big switch statement:

CASE (Bmult):
      BEFORE_POTENTIAL_GC ();
      DISCARD (1);
      TOP = Ftimes (2, &TOP);
      AFTER_POTENTIAL_GC ();
      NEXT;

"Ftimes" is defined as:

DEFUN ("*", Ftimes, Stimes, 0, MANY, 0,
doc: /* Return product of any number of arguments, which are numbers or markers.
usage: (* &rest NUMBERS-OR-MARKERS)  */)
(ptrdiff_t nargs, Lisp_Object *args)
{
    return arith_driver (Amult, nargs, args);
}

Arithmetic driver:

static Lisp_Object
arith_driver (enum arithop code, ptrdiff_t nargs, Lisp_Object *args)
{
  Lisp_Object val;
  ptrdiff_t argnum, ok_args;
  EMACS_INT accum = 0;
  EMACS_INT next, ok_accum;
  bool overflow = 0;

  switch (code)
    {
    case Alogior:
    case Alogxor:
    case Aadd:
    case Asub:
      accum = 0;
      break;
    case Amult:
    case Adiv:
      accum = 1;
      break;
    case Alogand:
      accum = -1;
      break;
    default:
      break;
    }

  for (argnum = 0; argnum < nargs; argnum++)
    {
      if (! overflow)
    {
      ok_args = argnum;
      ok_accum = accum;
    }

      /* Using args[argnum] as argument to CHECK_NUMBER_... */
      val = args[argnum];
      CHECK_NUMBER_OR_FLOAT_COERCE_MARKER (val);

      if (FLOATP (val))
    return float_arith_driver (ok_accum, ok_args, code,
                   nargs, args);
      args[argnum] = val;
      next = XINT (args[argnum]);
      switch (code)
    {
    case Aadd:
      overflow |= INT_ADD_WRAPV (accum, next, &accum);
      break;
    case Asub:
      if (! argnum)
        accum = nargs == 1 ? - next : next;
      else
        overflow |= INT_SUBTRACT_WRAPV (accum, next, &accum);
      break;
    case Amult:
      overflow |= INT_MULTIPLY_WRAPV (accum, next, &accum);
      break;
    case Adiv:
      if (! (argnum || nargs == 1))
        accum = next;
      else
        {
          if (next == 0)
        xsignal0 (Qarith_error);
          if (INT_DIVIDE_OVERFLOW (accum, next))
        overflow = true;
          else
        accum /= next;
        }
      break;
    case Alogand:
      accum &= next;
      break;
    case Alogior:
      accum |= next;
      break;
    case Alogxor:
      accum ^= next;
      break;
    case Amax:
      if (!argnum || next > accum)
        accum = next;
      break;
    case Amin:
      if (!argnum || next < accum)
        accum = next;
      break;
    }
    }

  XSETINT (val, accum);
  return val;
}

INT_MULTIPLY_WRAPV does multiplication via following code:

/* Return A <op> B, where the operation is given by OP.  Use the
   unsigned type UT for calculation to avoid overflow problems.
   Convert the result to type T without overflow by subtracting TMIN
   from large values before converting, and adding it afterwards.
   Compilers can optimize all the operations except OP.  */
#define _GL_INT_OP_WRAPV_VIA_UNSIGNED(a, b, op, ut, t, tmin, tmax) \
  (((ut) (a) op (ut) (b)) <= (tmax) \
   ? (t) ((ut) (a) op (ut) (b)) \
   : ((t) (((ut) (a) op (ut) (b)) - (tmin)) + (tmin)))

Every time "mult" is executed it goes through switch statement, wrapper code with many additional instructions when it only needs to execute one x86 instruction. In provided code Garbage Collection was not executed at all (judging by variable gcs-done).

Potential bottlenecks: checking if number is float, checking for overflow, switch statements.

I used portions of GPL licensed code from GNU Emacs for education purposes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.