Skip to content

map over a large list takes quadratic time #140

Open

Description

@andrefranken

Version: cel-expr-python 0.1.4 (wheel from PyPI), Linux x86_64, CPython 3.12.13.

What happens

The time to evaluate a map over a list grows quadratically with the size of the list. Measured with the expression l.map(x, x * 2):

items time
1,000 about 27 ms
4,000 about 255 ms
9,999 0.8 to 1.4 s

The comprehension iteration budget (10,000 iterations) bounds the number of iterations, but not the time: a list just under the budget already takes around a second.

How we measured

A script along these lines:

import time
import cel_expr_python.cel as cel

env = cel.NewEnv()
program = env.compile("l.map(x, x * 2)", disable_check=True)
for n in (1_000, 2_000, 4_000, 8_000):
    data = {"l": list(range(n))}
    start = time.perf_counter()
    program.eval(data=data)
    print(n, round((time.perf_counter() - start) * 1000), "ms")

Expected

Time roughly linear in the number of items.

Possible cause (not confirmed in the cel-cpp source)

The curve suggests the accumulator (@result + [x]) is copied on every step. cel-cpp has an option to append to the list in place (enable_comprehension_list_append), which does not seem to be enabled by the Python binding. We only measured map on large lists; we would expect filter to behave the same way, since it builds its result the same way.

Request

Enable the list-append optimisation in the binding, or expose it as an option.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions