ANN: Dogelog Runtime, Prolog to the Moon (2021)

[Greg Ewing]

On 16/09/21 4:23 am, Mostowski Collapse wrote:
> I really wonder why my Python implementation
> is a factor 40 slower than my JavaScript implementation.

There are Javascript implementations around nowadays that are
blazingly fast. Partly that's because a lot of effort has been
put into them, but it's also because Javascript is a different
language. There are many dynamic aspects to Python that make
fast implementations difficult.

> I use in Python:
> 
>    temp = [NotImplemented] * code[pos]
>    pos += 1
> 
> is the the idiom [_] * _ slow?

No, on the contrary it's probably the fastest way to do it
in Python. You could improve it a bit by precomputing
[NotImplemented]:

# once at the module level
NotImplementedList = [NotImplemented]

# whenever you want a new list
temp = NotImplementedList * code[pos]

That's probably at least as fast as built-in function for
creating lists would be.

> does it really first create an
> array of size 1 and then enlarge it?

It does:

 >>> def f(code, pos):
...  return [NotImplemented] * code[pos]
...
 >>> from dis import dis
 >>> dis(f)
   2           0 LOAD_GLOBAL              0 (NotImplemented)
               2 BUILD_LIST               1
               4 LOAD_FAST                0 (code)
               6 LOAD_FAST                1 (pos)
               8 BINARY_SUBSCR
              10 BINARY_MULTIPLY
              12 RETURN_VALUE

BTW, the Python terminology is "list", not "array".
(There *is* something in the stdlib called an array, but
it's rarely used or needed.)

-- 
Greg