cchianel
- Does several warm-up runs so the JIT-optimized code is benchmarked instead of the interpreted code/compilation.
- Create multiple forks of the JVM to eliminate JVM run variance.
- Provide utilities like `Blackhole` to prevent dead code elimination and `State` to do setup and prevent constant folding.
If you want to try to implement one yourself, a simple one is Simulated Annealing [1]. The core algorithm shouldn't be more than 30 lines of code; it is simple to implement. If you want to try an existing library, you can try Timefold Solver [2] (disclosure: I work for Timefold).
Note: the code itself is far from production ready, do not use this!
As an example of how it can be used, you can look at https://github.com/Christopher-Chianelli/timefold-wasm-servi... and https://github.com/Christopher-Chianelli/timefold-wasm-c-cli..., which was an experiment I did to try using C code inside Timefold Solver (a Java library that can be used to solve constraint problems like Employee Scheduling and Vehicle Routing).
Examples include:
- School Timetabling
- Employee Scheduling
- Conference Scheduling
- Flight Crew Scheduling
Metaheurstics are also very useful for puzzle games; you can quickly run a metaheuristic to generate a difficult but solvable puzzle in less than a second, while only being about 20 lines of code without libraries (but as your scale increases to hundreds of different pieces, you probably want a library so you can use their incremental calculation).
This basically means you have two choices:
1. Translate the constraints from the new language to Java bytecode at runtime. 2. Translate the entire solver to a new language.
We did (1) for a bit for CPython, but since CPython bytecode constantly change and break (and is so poorly documented) it was a nightmare to maintain. You can find a blog post of me explaining it a bit more here: https://timefold.ai/blog/java-vs-python-speed. The CPython port is no longer maintained, and has quite a few missing features.
That being said, we have a wide range of ready made models that you can access via an API, which might fit your use case (you can see a list at https://docs.timefold.ai/).
Metaheuristic solvers are different in that you don't need to model your problem as a mixed integer problem. Instead, all it cares about is having a function that returns something you can compare. This allows you to model your problem however you like. Some metaheurstic techniques include Simulated Annealing, Late Acceptance Local Search, and Tabu Search.
Metaheuristic solvers may not generate optimal solutions (after all, by their nature, they don't know the structure of the problem), but they generate "good enough" and "close to optimal" solutions. Metaheurstic solvers tends to beat MIP and CP-SAT for VRP, whereas MIP and CP-SAT are better for bin packing.
If you want to try using a Metaheuristic solver, I can recommend Timefold, which allows you to define your constraints using your domain objects in an incremental matter (it has SQL/Java-Streams like syntax, which in my opinion, is more readable than formulas) (disclosure: I work for Timefold).
var score = 0;
for (var shiftA : solution.getShifts()) {
for (var shiftB : solution.getShifts()) {
if (shiftA != shiftB && shiftA.getEmployee() == shiftB.getEmployee() && shiftA.overlaps(shiftB)) {
score -= 1;
}
}
}
return score
That being said, it might be useful for a move selector. I need to give it a more in depth reading.
So if I understand correct, it states that all optimization algorithm must choose an order to evaluate solutions, and the faster it evaluates the "best" solution, the "better" the algorithm.
For example, say the search space is {"a", "b", "c"} and the best solution is "c". Then there are 3! (6) ways to evaluate all solutions:
"a", "b", "c"
"a", "c", "b"
"b", "a", "c"
"b", "c", "a"
"c", "a", "b"
"c", "b", "a"
(of course, in a real problem, the search space is much, MUCH larger).
The way Timefold tackles this is move selectors. In particular, you can design custom moves that uses knowledge of your particular problem which in turn affect when certain solutions are evaluated. Additionally, you can design custom phases that runs your own algorithm and then pass the solution found to local search. One of the projects we are working on currently is the neighborhood API, to make it much easier to write your own custom moves. That being said, for most problems that humans deal with, you don't need to configure Timefold and just work with the defaults (which is best-fit followed by a late acceptance local search with change and swap moves).
For what it's worth: metaheuristics solvers tend to be better than linear solvers for shift scheduling and vehicle routing, but worse for bin packing. But it still works, and is still fast.
There cannot be a guarantee to find a solution to a given percentage worse than optimal for a fully general problem, since you would need to know optimal to give such a guarantee (and since the problem fully general, you cannot use the structure of the problem to reduce it).
Most constraint problems have many feasible solutions, and have a way to judge how much worse or better one solution is to another.
There are good and bad way to write constraints.
One bad way to write constraints is score traps, where between one clearly better solution has the same score as a clearly worse solution.
For example, for shift scheduling, a solution with only 1 overlapping shift with the same employee is better than a solution with 2 overlapping shifts with the same employee.
A bad score function would penalize both solutions by 1, meaning a solver have no idea which of the two solutions are better.
A good score function would penalize the schedule with 1 overlapping shift with the same employee by 1, and the schedule with 2 overlapping shifts with the same employee by 2.
The class of problems I am talking about is the class of problems where you can assign a score to a possible solution, with limited score traps.
Timefold has no guarantees about finding a solution in reasonable time (but unless you done something terribly wrong or have a truly massive dataset, it finds a good solution really quickly 99.99% of the time). Instead, you set the termination condition of the solver; it could be time-based (say 60 minutes), unimproved time spent (solve until no new better solutions are found after 60 minutes), or the first feasible solution (there are other termination conditions that can be set).
If so, I agree it is impossible for a fully general problem solver to find the optimal solution to a problem in a reasonable amount of time (unless P = NP, which is unlikely).
However, if a "good enough" solution that is only 1% worse than optimal works, then a fully general solver can do the job in a reasonable amount of time.
One such example of a fully general solver is Timefold; you express your constraints using plain old Java objects, so you can in theory do whatever you want in your constraint functions (you can even do network calls, but that is extremely ill-advised since that will drastically slow down score calculation speeds).
Disclosure: I work for Timefold.
- "Essentials of Metaheuristics" by Sean Luke https://cs.gmu.edu/~sean/book/metaheuristics/
- "Clever Algorithms" by Jason Brownlee https://cleveralgorithms.com/
Timefold uses the metaheuristic algorithms in these books (Tabu Search, Late Acceptance, Simulated Annealing, etc.) to find near-optimal solutions quickly from a score function (typically defined in a Java stream-like/SQL-like syntax so score calculation can be done incrementally to improve score calculation speed).
You can see simplified diagrams of these algorithms in action in Timefold's docs: https://docs.timefold.ai/timefold-solver/latest/optimization....
Disclosure: I work for Timefold.
Archipelago GitHub: https://github.com/ArchipelagoMW/Archipelago
- In Python 3.10, jumps changed from absolute indices to relative indices
- In Python 3.11, cell variables index is calculated differently for cell variables corresponding to parameters and cell variables corresponding to local variables
- In Python 3.11, MAKE_FUNCTION has the code object at the TOS instead of the qualified name of the function
For what it's worth, I created a detailed behaviour of each opcode (along with example Python sources) here: https://github.com/TimefoldAI/timefold-solver/blob/main/pyth... (for up to Python 3.11).
- The vast majority of code generation would have to be dynamic dispatches, which would not be too different from CPython's bytecode.
- Types are dynamic; the methods on a type can change at runtime due to monkey patching. As a result, the compiler must be able to "recompile" a type at runtime (and thus, you cannot ship optimized target files).
- There are multiple ways every single operation in Python might be called; for instance `a.b` either does a __dict__ lookup or a descriptor lookup, and you don't know which method is used unless you know the type (and if that type is monkeypatched, then the method that called might change).
A JIT compiler might be able to optimize some of these cases (observing what is the actual type used), but a JIT compiler can use the source file/be included in the CPython interpreter.
- CPython Bytecode is far from stable; it changes every version, sometimes changing the behaviour of existing bytecodes. As a result, you are pinned to a specific version of Python unless you make multiple translators.
- CPython Bytecode is poorly documented, with some descriptions being misleading/incorrect.
- CPython Bytecode requires restoring the stack on exception, since it keeps a loop iterator on the stack instead of in a local variable.
I recommend instead doing CPython AST → PySM Assembly. CPython AST is significantly more stable.
- In OR Tools, you need to write your constraints as mathematical equations. You can only provide your own function in a few scenarios, such as calculating the distance between two points. This allows OR Tools to eliminate symmetries and calculate gradients to improve its solution search. In Timefold, your constraints are treated like a black box, so your constraints can use any function and call any library you like (although you shouldn't do things like IO in them). However, since said constraints are a black box, Timefold is unable to eliminate symmetries or calculate gradients.
- In OR Tools, you have very little control in how it does its search. At most, you can select what algorithm/strategy it uses. In Timefold, you have a ton of control in how it does its search: from what moves its tries to adding your own custom phases. If none are configured, it will use sensible defaults. That being said, certain problems strongly benefit from custom moves.
- In OR Tools, you do not need to create custom classes; you create variables using methods on their domain model classes. In Timefold, you need to define your domain model by creating your own classes. This adds initial complexity, but it makes the code more readable: instead of your variable being an int, it is an Employee or a Visit. That being said, it can be difficult for someone to design an initial model, since it requires an understanding of the problem they are solving.
All in all, when using Timefold, you need to think in a more declarative approach (think Prolog, SQL, etc). For example, let say you have a room assignment problem where a teacher can only teach at a single room at once, and minimize room changes. In Timefold, it may look like this:
# Typically would be stored in a parameterization object, but a global var
# is used for brevity
teacher_count = 3
@planning_entity
@dataclass
class Room:
id: Annotated[int, PlanningId]
date: int
name: str
# This can also be a Teacher object, but str is used for brevity here
teacher: Annotated[str, PlanningVariable] = field(default=None)
@planning_solution
@dataclass
class Timetable:
rooms: Annotated[list[Room], PlanningEntityCollectionProperty]
teachers: Annotated[list[str], ValueRangeProvider]
score: Annotated[HardSoftScore, PlanningScore] = field(default=None)
@constraint_provider
def timetable_constraints(cf: ConstraintFactory):
return [
cf.for_each_unique_pair(Room, Joiners.equal(lambda room: room.date), Joiners.equal(lambda room: room.teacher))
.penalize(HardSoftScore.ONE_HARD)
.as_constraint('Teacher time conflict'),
cf.for_each_unique_pair(Room, Joiners.equal(lambda room: room.teacher))
.filter(lambda a, b: a.name != b.name)
.penalize(HardSoftScore.ONE_SOFT)
.as_constraint('Minimize room change')
]
solver_config = SolverConfig(
solution_class=Timetable,
entity_class_list=[Room],
score_director_factory_config=ScoreDirectorFactoryConfig(
constraint_provider_function=timetable_constraints
),
termination_config=TerminationConfig(
spent_limit=Duration(seconds=5)
)
)
solver_factory = SolverFactory.create(solver_config)
solver = solver_factory.build_solver()
problem: Timetable = build_problem()
solver.solve(problem)
teacher_count = 3
problem: Timetable = build_problem()
model = cp_model.CpModel()
objective = []
room_vars = [cp_model.model.new_int_var(0, teacher_count - 1, f'room_assignment_{i}' for i in range(len(problem.rooms)))]
room_vars_by_date = {date: [room_vars[i] for i in range(len(problem.rooms)) if problem.rooms[i].date == date] for date in {room.date for room in problem.rooms}}
room_vars_by_name = {name: [room_vars[i] for i in range(len(problem.rooms)) if problem.rooms[i].name == name] for name in {room.name for room in problem.rooms}}
for date, date_vars in room_vars_by_date.items():
model.AddAllDifferent(date_vars)
for name, name_vars in room_vars_by_name.items():
for assignment_1 in names_vars:
for assignment_2 in names_vars:
if assignment_1 is not assignment_2:
objective.add(assignment_1 != assignment_2)
model.minimize(sum(objective))
solver = cp_model.CpSolver()
status = solver.solve(model)Using IPC for all internal calls would probably take significant overhead; the user functions are typically small (think `lambda shift: shift.date in employee.unavailable_dates` or `lambda lesson: lesson.teacher`). Depending on how many constraints you have and how complicated your domain model is, there could be potentially hundreds of context switches for a single score calculation. It might be worth prototyping though.
- The Java side needs to store opaque Python pointers which may have no references on the CPython side.
- The CPython side need to store generated proxies for some Java objects (the result of constraint collectors, which are basically aggregations of a solution's data).
Solving runs a long time, typically at least a hour (although you can modify how long it runs for). If we don't free memory (by releasing the opaque Python Pointer return values), we will quickly run out of memory after a couple of minutes. The only way to free memory on the Java side is to close the arena holding the opaque Python pointer. However, when that arena is closed, its memory is zeroed out to prevent use-after-free. As a result, if CPython haven't garbage collected that pointer yet, it will cause a segmentation fault on the next CPython garbage collection cycle.
JPype (a CPython -> Java bridge) does dark magic to link the JVM's and CPython's garbage collector, but has performance issues when calling a CPython function inside a Java function, since its proxies have to do a lot of work. Even GraalPy, where Python is ran inside a JVM, has performance issues when Python calls Java code which calls Python code.
A direct FFI call using JNI or the new foreign interface is fast, and has roughly the same speed as calling a Java method directly. Alas, the CPython and Java garbage collectors do not play nice, and require black magic in order to keep them in sync.
On the other hand, using proxies (such as in JPype or GraalPy) cause a significant performance overhead, since the parameters and return values need to be converted, and might cause additional FFI calls (in the other direction). The fun thing is if you pass a CPython object to Java, Java has a proxy to the CPython object. And if you pass that proxy back to CPython, a proxy to that proxy is created instead of unwrapping it. The result: JPype proxies are 1402% slower than calling CPython directly using FFI, and GraalPy proxies are 453% slower than calling CPython directly using FFI.
What I ultimately end up doing is translating CPython bytecode into Java bytecode, and generating Java data structures corresponding to the CPython classes used. As a result, I got a 100x speedup compared to using proxies. (Side note: if you are thinking about translating/reading CPython bytecode, don't; it is highly unstable, poorly documented, and its VM has several quirks that make it hard to map directly to other bytecodes).
For more details, you can see my blog post on the subject: https://timefold.ai/blog/java-vs-python-speed
- CPython's bytecode is extremely unstable. Not only do new opcodes are added/removed each release, the meaning of existing opcodes can change. For instance the meaning for the argument to JUMP_IF_FALSE_OR_POP changes depending on the CPython version; in CPython 3.10 and below, it is an absolute address, in CPython 3.11 and above, it a relative address.
- The documentation for the bytecode in dis tends to be outdated or outright wrong. I often had to analyze the generated bytecode to figure out what each opcode means (and then submit a corresponding PR to update said documentation). Moreover, it assumes you know how the inner details of CPython work, from the descriptor protocol to how binary operations are implemented (each of which are about 30 lines functions when written in Python).
- CPython's bytecode is extremely atypical. For instance, a for-loop keeps its iterator on the stack instead of storing it in a synthetic variable. As a result, when an exception occurs inside a for-loop, instead of the stack containing only the exception, it will also contain the for-loop iterator.
As for why I did this, I have Java calling CPython in a hot loop. Although direct FFI is fast, it causes a memory leak due to Java's and Python's Garbage collectors needing to track each other's objects. When using JPype or GraalPy, the overhead of calling Python in a Java hot-loop is massive; I got a 100x speedup from translating the CPython bytecode to Java bytecode with identical behaviour (details can be found in my blog post: https://timefold.ai/blog/java-vs-python-speed).
I strongly recommend using the AST instead (although there are no backward comparability guarantees with AST, it is far less likely to break between versions).
I don't think Ada program is available as an example though, so you'll need to input it manually.
Fun fact: my compiler course project was creating a C compiler targeting the emulator https://github.com/Christopher-Chianelli/ccpa (warning, said code is terrible).
- Use a boolean variable that is true if and only if a particular employee is assigned to a particular shift. For 2 shifts (A, B) and 2 employees (Amy, Beth), the variables would be Amy_A, Amy_B, Beth_A, Beth_B
- Use an int variable, where each employee is mapped to a number. For 2 shifts (A, B) and 3 employees (Amy, Beth, Carl), the variables would be A, B (which will have value 0 for Amy, 1 for Beth, 2 for Carl).
Using an int variable is usually better, since it automatically encodes the "each shift must have exactly one employee constraint" which would otherwise need to be added. That being said, sometimes the boolean model is used so a SAT solver can be used instead of a Integer Linear Programming Solver.
Typically, for theorem based solvers (such as Z3 or OR Tools), you add a group of similar constraints in a loop where you iterate through relevant variables. For instance, to add constraints for overlapping shifts, you would have a directory mapping each shift to the shifts its overlaps, and add a not equals constraint for each pair (since if they are equal, they have the same employee, and employees usually are unable to be at two places at the same time).
for shift in shift_vars:
for overlapping_shift in overlapping_shifts[shift]:
solver.add(shift != overlapping_shift)
@planning_entity
@dataclass
class Shift:
employee: Annotated[Employee, PlanningVariable]
start: datetime
end: datetime
def overlaps(self, other: 'Shift') -> bool:
return self.start < other.end and other.start < self.end
def no_overlapping_shifts(constraint_factory: ConstraintFactory):
return (constraint_factory.for_each(Shift)
.join(Shift,
Joiners.equal(lambda shift: shift.employee))
.filter(lambda a, b: a.overlaps(b))
.penalize(HardSoftScore.ONE_HARD)
.as_constraint('Overlapping Shift'))
I am unfortunately very familiar with CPython's bytecode [1], and do not recommend trying to do anything with it:
- It is extremely unstable; the same opcodes might do different things between versions. For instance: for the opcode `JUMP_IF_TRUE_OR_POP`, in Python 3.10 and below, its argument is an absolute address. In Python 3.11 and above, it is a relative address.
- It does not have synthetic (compiler-introduced) variables; this means the iterator of a loop must be kept on the stack, and as a result, exception handling must keep some items (namely, the iterators) on the stack.
- It is poorly documented (although it is getting better nowadays); there where numerous times where the stack layout an opcode expected changed between versions but were not yet included in the dis documentation.
One notable difference between CPython and other bytecode interpreters is a lack of multiple compilers. For instance, in Java, there are typically three compilers:
- `javac`, which produce class files that are interpreted by a basic, slow virtual machine.
- C1, which generates instrumented machine code to collect profiling data that C2 will use (still relatively slow).
- C2, which generates optimized machine code from the profiling data of C1 (significantly faster than C1).
CPython shoves the job of all three into its single interpreter. For instance, its CACHE instruction serves the purpose of recording the types on the stack for the subsequent instruction, which the specializing adaptive interpreter [2] uses to specialize an opcode (for instance, BINARY_OP to BINARY_OP_INPLACE_ADD_UNICODE).
All of the above makes it extremely hard to develop against CPython's bytecode, and is probably why there are few libraries for reading or transforming CPython's bytecode. Although most modifications can be done by either modifying the class object directly, wrapping the class/function, or extending the class, some cannot. For example:
- Change calls of function `foo` to function `bar`.
- Compute the automatic differentiation of a function [3].
- Translate python code blocks to another language for interoperability (for instance, to Java or SQL).
The way most library authors do it instead is by reading the AST, which is mostly stable.
[1] https://github.com/TimefoldAI/timefold-solver/tree/main/pyth..., a Python bytecode to Java bytecode translator, written to avoid excessive overhead caused by FFI calls (the new foreign Java API largely removes the overhead).
This is useful to determining maximum concurrent use of a resource; for instance, if there are only 3 projectors, a maximum of 3 lessons that require projectors can overlap at any given time.
The basic idea is to use a sorted multi-set of each interval's end points, doing case analysis on insertion to determine what interval clusters to merge; removal re-computes the entire cluster the removed range was in, splitting the cluster into two or more when gaps are encountered.
For the implementation, see https://github.com/TimefoldAI/timefold-solver/blob/main/core...
As a side effect of keeping track of connected clusters, the data structure also keeps track of gaps between clusters (which could be used to find the next availability).
For how it is used in practice, there an example in Timefold's docs: https://docs.timefold.ai/timefold-solver/latest/constraints-...
A simpler algorithm can be used when each interval represent a time grain (fixed length, no two intervals overlap). See https://github.com/TimefoldAI/timefold-solver/tree/main/core... for that.