Parallel Computing: Difference between revisions

From MemCP
Jump to navigation Jump to search
(Created page with "Almost 99% of all newly invented are imperative programming languages. But imperative languages have one drawback: their parallelization is hard. == Drawbacks of Imperative Programming Languages == Imperative programming languages do have one mayor drawback: state. The concept of an imperative language is that commands are executed which change the content of variables or complex objects in the memory. When trying to create an optimizing compiler that from itself finds...")
 
(Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference)
 
Line 1: Line 1:
Almost 99% of all newly invented are imperative programming languages. But imperative languages have one drawback: their parallelization is hard.
<!-- Copyright (C) 2026 Carl-Philip Haensch -->
<!-- SPDX-License-Identifier: GPL-3.0-or-later -->
= Parallel Computing =


== Drawbacks of Imperative Programming Languages ==
MemCP evaluates independent functional work in parallel when the planner and runtime can prove that doing so is safe and useful. Storage operators process columns in batches and distribute sufficiently large shard work over a bounded worker set. Small batches remain local because scheduling may cost more than the work itself.
Imperative programming languages do have one mayor drawback: state. The concept of an imperative language is that commands are executed which change the content of variables or complex objects in the memory. When trying to create an optimizing compiler that from itself finds parallelizable parts in the code, the compiler has to keep track of data dependencies and the random side effects of each command and function call.


The possibly simplest solution to this problem is to tell the compiler exactly which loops are parallelizable. This however forces the developer to write nearly side-effect-free code. So we decided to go the pure way – to '''design a programming language that does not allow side-effects.'''
Functional code makes dependencies explicit: a function result follows from its inputs instead of hidden mutation of shared outer variables. That allows the runtime to run independent branches concurrently and combine their values later. Explicit shared state still exists through sessions, locks, caches, I/O, and storage writes, so “written in Scheme” does not by itself make an arbitrary callback parallel-safe.


== The Functional World ==
MemCP's dialect was shaped around that property: imperative outer-scope mutation was omitted, <code>set</code> creates a scope-local binding, <code>begin</code> provides a local environment, and Scheme values/code can be serialized. Serialization is useful for cached/generated programs and is also a prerequisite for the planned remote scan model, but it does not by itself make multi-node execution available today.
A "pure" functional programming language is a language where every function will compute its result only and only from its inputs. This builds a great basis for highly parallel map-reduce algorithms like we need in our clusterable in-memory database.


We took the scheme interpreter from Pieter Kelchtermans written in golang and added some extra features:
Scan pipelines propagate request cancellation and early-stop conditions rather than always materializing every matching row. Nested scans and transaction-bound operations use bounded fanout to avoid goroutine explosion and lock cycles. Parallel reducers combine per-worker results using explicit neutral values and reduction functions.


* We removed the <code>set!</code> instruction because it is the only function to cause global side effects All other functions are local to the current environment and as long as you don’t change the environment, every piece of code can be run in parallel without affecting each other
== Parallel primitives and scans ==
* We made <code>begin</code> to open its own environment, so self recursion can be done by defining a function in a begin block (<code>!begin</code> is the scopeless version)
* We fixed <code>if</code>
* We also allowed strings as native datatypes as well as the <code>concat</code> function which will concatenate all strings to one string
* We added a serialization mechanism to fully recover values and turn them into valid scheme code again.


'''carli@launix-MS-7C51''':'''~/projekte/memcp/server-node-golang'''$ make
* <code>parallel</code> evaluates independent expressions and waits for their results.
go run *.go
* <code>parallel_map</code> and <code>parallelN</code> distribute sufficiently large collection work with bounded fanout.
> 45
* <code>scan</code> performs shard-local filter/map/reduce work and combines shard results in a second reduction phase.
==> 45
* <code>scan_order</code> can parallelize eligible filtering/order preparation while preserving the serial order required by output and reduction.
> (+ 1 2)
* <code>newsession</code>, <code>once</code>, and <code>mutex</code> provide explicit coordination when state must be shared.
==> 3
> (define currified_add (lambda (a) (lambda (b) (+ a b))))
==> "ok"
> ((currified_add 4) 5)
==> 9
> (define add_1 (currified_add 1))
==> "ok"
> (add_1 6)
==> 7
> (add_1 (add_1 3))
==> 5
> (define name "Peter")
==> "ok"
> (concat "Hello " name)
==> "Hello Peter"
>  


== MemCP functions that support parallelism ==
Choose an associative reducer and a correct neutral element. Floating-point addition, string concatenation, first/last selection, and side-effecting callbacks can produce order-sensitive results; the SQL planner retains serial boundaries where semantics require them.
The following functions support parallelism:


* <code>scan</code> runs <code>filter</code>, <code>map</code> and <code>reduce</code> in parallel for each shard, <code>reduce2</code> is serial
Supported hot Scheme procedures may be compiled by the native x86-64 JIT. Compilation and guarded specialization are optional optimizations; unsupported procedures continue in the interpreter. None of these mechanisms promises linear scaling with core count: memory bandwidth, cardinality, compression, synchronization, query shape, and physical plan determine the result.
* <code>scan_order</code> runs <code>filter</code> as well as the sorting in parallel and <code>map</code> and <code>reduce</code> in serial
* <code>parallel</code> evaluates each given parameter in parallel and continues if all jobs are done
* <code>newsession</code> is a threadsafe key-value store to share context over threads
* <code>once</code> and <code>mutex</code> help to synchronize control flow


You can read the manual by typing <code>(help "scan")</code> in the scheme console.
Publish repeatable measurements rather than a fixed speed-up. See [[Performance Measurement]], [[Query Planner and Physical Lowering]], and [[JIT Compilation]].
 
== Conclusion ==
What did we achieve?
 
* We chose scheme to be our language of choice
* We stripped away those parts from scheme that make it unsafe for parallel computing
* We added some useful functions to scheme to fit our needs (string processing, parallelization primitives…)
* We implemented a serialization function that can recreate scheme code from memory objects that can be loaded on other machines
* Now we can start implementing our highly-parallel map-reduce algorithms that can take map and reduce lambda-functions, execute them in parallel and enjoy the highly parallel result

Latest revision as of 11:59, 28 August 2026

Parallel Computing

MemCP evaluates independent functional work in parallel when the planner and runtime can prove that doing so is safe and useful. Storage operators process columns in batches and distribute sufficiently large shard work over a bounded worker set. Small batches remain local because scheduling may cost more than the work itself.

Functional code makes dependencies explicit: a function result follows from its inputs instead of hidden mutation of shared outer variables. That allows the runtime to run independent branches concurrently and combine their values later. Explicit shared state still exists through sessions, locks, caches, I/O, and storage writes, so “written in Scheme” does not by itself make an arbitrary callback parallel-safe.

MemCP's dialect was shaped around that property: imperative outer-scope mutation was omitted, set creates a scope-local binding, begin provides a local environment, and Scheme values/code can be serialized. Serialization is useful for cached/generated programs and is also a prerequisite for the planned remote scan model, but it does not by itself make multi-node execution available today.

Scan pipelines propagate request cancellation and early-stop conditions rather than always materializing every matching row. Nested scans and transaction-bound operations use bounded fanout to avoid goroutine explosion and lock cycles. Parallel reducers combine per-worker results using explicit neutral values and reduction functions.

Parallel primitives and scans

  • parallel evaluates independent expressions and waits for their results.
  • parallel_map and parallelN distribute sufficiently large collection work with bounded fanout.
  • scan performs shard-local filter/map/reduce work and combines shard results in a second reduction phase.
  • scan_order can parallelize eligible filtering/order preparation while preserving the serial order required by output and reduction.
  • newsession, once, and mutex provide explicit coordination when state must be shared.

Choose an associative reducer and a correct neutral element. Floating-point addition, string concatenation, first/last selection, and side-effecting callbacks can produce order-sensitive results; the SQL planner retains serial boundaries where semantics require them.

Supported hot Scheme procedures may be compiled by the native x86-64 JIT. Compilation and guarded specialization are optional optimizations; unsupported procedures continue in the interpreter. None of these mechanisms promises linear scaling with core count: memory bandwidth, cardinality, compression, synchronization, query shape, and physical plan determine the result.

Publish repeatable measurements rather than a fixed speed-up. See Performance Measurement, Query Planner and Physical Lowering, and JIT Compilation.

Retrieved from "https://www.memcp.org/index.php?title=Parallel_Computing&oldid=347"