Expression should provide a thread-safe api

[xuanswe]

I have an expression and I need to calculate results for a lot of cases of variables.

For example,

val expression = Expression("a + b")

// thread 1
thread {
  expression.with("a", 1)
  expression.with("b", 1)
}

// thread 2
thread {
  expression.with("a", 2)
  expression.with("b", 2)
}

// ...

// thread n
thread {
  // ...
}

If I understand the implementation correctly, it will not work because Expression object is not safe to be used in multi threads.
Could we make it thread-safe? Maybe Expression should allow to build immutable snapshots with a list of variables. The snapshots should reuse the expensive computation from Expression to evaluate the result.

[uklimaschewski]

In fact, an expression is thread-safe, as soon as the expression was parsed.
But the standard MapBasedDataAccessor which holds the variable values is not thread-safe.

There are some possibilities to achieve thread safety here. I did a small test with a custom data accessor that is using ThreadLocal to store the data along with the thread:

package com.ezylang.evalex;

import com.ezylang.evalex.config.ExpressionConfiguration;
import com.ezylang.evalex.data.DataAccessorIfc;
import com.ezylang.evalex.data.EvaluationValue;
import com.ezylang.evalex.data.MapBasedDataAccessor;
import com.ezylang.evalex.parser.ParseException;
import org.junit.jupiter.api.Test;

import java.math.BigDecimal;
import java.security.SecureRandom;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

import static org.assertj.core.api.Assertions.assertThat;

public class ThreadLocalTest {

  class ThreadLocalDataAccess implements DataAccessorIfc {
    ThreadLocal<MapBasedDataAccessor> threadLocal =
        ThreadLocal.withInitial(MapBasedDataAccessor::new);

    @Override
    public EvaluationValue getData(String variable) {
      return threadLocal.get().getData(variable);
    }

    @Override
    public void setData(String variable, EvaluationValue value) {
      threadLocal.get().setData(variable, value);
    }
  }

  @Test
  void testThreadLocal() throws ParseException, InterruptedException {

    ExpressionConfiguration configuration =
        ExpressionConfiguration.builder().dataAccessorSupplier(ThreadLocalDataAccess::new).build();

    Expression expression = new Expression("a+b", configuration);
    // validate makes sure the expression is parsed before entering the multi-threaded code
    expression.validate();

    SecureRandom random = new SecureRandom();
    // start 100 threads
    ExecutorService es = Executors.newCachedThreadPool();
    for (int t = 0; t < 100; t++) {
      es.execute(
          () -> {
            try {
              System.out.println("Starting with " + Thread.currentThread().getName());
              for (int i = 0; i < 10000; i++) {
                BigDecimal a = new BigDecimal(random.nextInt());
                BigDecimal b = new BigDecimal(random.nextInt());
                EvaluationValue result = expression.with("a", a).and("b", b).evaluate();

                BigDecimal sum = a.add(b);
                assertThat(result.getStringValue()).isEqualTo(sum.toPlainString());
              }
              System.out.println("Done with " + Thread.currentThread().getName());
            } catch (EvaluationException e) {
              throw new RuntimeException(e);
            } catch (ParseException e) {
              throw new RuntimeException(e);
            }
          });
    }
    es.awaitTermination(10, TimeUnit.SECONDS);
  }
}

To test, I started 100 threads and each one is doing 10,000 calculations with random values.
If you do not use the ThreadLocalDataAccess in configuration, there are a lot of errors, because all threads try to read and write to the same map.
When using ThreadLocalDataAccess, then there are no errors because each thread has now its own map of data.

[xuanswe]

Isn't that too much for users?
Should it be just automatically thread-safe without doing anything from usage side?
If users want to switch from Thread to whatever we don't know, ex. Kotlin coroutines, they will need to find a way to make it work.
If the lib support immutability approach, we don't need to care how users use the lib api. It will automatically be safe with any parallel programming frameworks (Java Thread, coroutines or whatever else we don't care).

[uklimaschewski]

EvalEx is a library for use by programmers. So, the user is somebody with programming skills. And as you point out, the environment where and how the library is used may differ. And the library user should be able to adopt to different scenarios.

The above thread safe solution might get a part of a future release, so that it can be configured without the need of an own implementation.

Immutability can only be an optional configuration, the current default flexibility allows for e.g. operators and functions with side effects. This was intentional.

But I will think of a more general immutable evaluation variant, shouldn't be too hard.

[xuanswe]

EvalEx is a library for use by programmers. So, the user is somebody with programming skills. And as you point out, the environment where and how the library is used may differ. And the library user should be able to adopt to different scenarios.

I don't totally agree with this. IMO, user has skill, doesn't mean s/he want to manage extra work for each environment. User would be happier if the internal of lib would produce the same thing regardless of where it is running.

Immutability can only be an optional configuration, the current default flexibility allows for e.g. operators and functions with side effects. This was intentional.

You don't need to have an "optional configuration". As I mentioned in previous comment, it's possible to create a snapshot from existing expression. The "snapshot" could reuse expensive computation result of the Expression instance as the starting point plus the provided variables to create the immutable state. The evaluation will be done with the immutable state of the snapshot. So, developers could simply pass around the snapshot to anywhere and it will just work without worrying about thread safe.
This is the powerful of immutability.

[jfisbein]

At least a clone() method that generates a new Expression but reuses the AST, should be easy to implement and useful for multi- thread environments.

[stevenylai]

This is also a nice to have in our current project so that we may create fewer Expression objects. In my opinion, we don't need to introduce new configs but we can instead implement a re-entrant / stateless API such as Expression.evaluateWith(Map<String, Object> variables). If the lib user only uses this function for evaluation, the Expression object will be semantically immutable. And in my opinion, it's quite obvious from the API which APIs are semantically immutable and which are not. Expression.with() and Expression.and() returns the same object so they are not semantically immutable APIs.

Moreover, I think such feature should go side-by-side with what we currently have and when used together, we can even allow partial evaluation / currying. As a simplistic example, consider if we have a function called LOG(base, n). Then:

var log2 = new Expression("LOG(base, n)").with(Map.of("base", 2));  // bind 2 to base

System.out.println(log2.evaluateWith("n", 3));  // log(2, 3)
System.out.println(log2.evaluateWith("n", 4));  // log(2, 4)

I think implementing such evaluateWith() API without changing existing behavior is not too difficult. In fact, I think I can make it work early next week (when I am WFH).

How does it sound for everyone?

[uklimaschewski]

@stevenylai You mean that this new Expression.evaluateWith(Map<String, Object> variables) method will create and use a new instance of the data accessor, copy over the values and then evaluate?
Or, maybe just create a new Expression clone (using the parsed AST) with only a new data accessor instance and then evaluate that cloned expression?

[stevenylai]

@uklimaschewski No need to copy anything. I mean something like this: https://github.com/ezylang/EvalEx/compare/main...stevenylai:EvalEx:evaluateWith?expand=1

The key point here is that library users don't have to use those stateful functions (with() and and()) to define variables for evaluation and they can instead provide variables on the fly (effectively making Expression semantically immutable).

We can then create one expression object but using it on multiple threads (since on each thread we don't have to update the object):

var expression = new Expression("a + b");

Thread1:

expression.evaluateWith(Map.of("a", 1, "b", 1));

Thread2:

expression.evaluateWith(Map.of("a", 2, "b", 2));

[uklimaschewski]

Thank you, but I think it would be easier and cleaner, if the evaluateWith() method would simply "clone" the expression (using a new constructor) and then use its own dataAccessor.

  public Expression(Expression expression) {
    this.expressionString = expression.getExpressionString();
    this.abstractSyntaxTree = expression.getAbstractSyntaxTree();
    this.configuration = expression.getConfiguration();
    this.dataAccessor = configuration.getDataAccessorSupplier().get();
    this.constants.putAll(configuration.getDefaultConstants());
  }

and then

  public EvaluationValue evaluateWith(Map<String, Object> values) throws EvaluationException, ParseException {
    Expression evaluateExpression = new Expression(this).withValues(values);
    return evaluateExpression.evaluate();
  }

I haven't tested this, just an idea. But it is just adding a constructor and a new function.

EDIT: Forgot to set the AST in constructor.

[stevenylai]

OK. I think your approach should also work for us.

Just one last thing, if the purpose is to copy the expression object, perhaps the new API should be called Expression copy() or implement Cloneable to be more explicit instead of going with evaluateWith()? Having copy() / clone() and the API can also allow users to get hold of the copied Expression object instead of just doing one-off evaluation.