For those asking "How the hell does OCaml not support multicore in 2015????", this is my reply, crossposted from /r/ocaml:
You can make OS level threads, but they can't be both running at the same time due to the GIL (Global Interpreter Lock). Then why are they even there you might ask? Because it allows you to do a blocking call on a thread and to keep executing other stuff in the main thread. Other languages that have a GIL (and the same restriction) are Javascript (including Node.js), Ruby and Python.
Now, IN PRACTICE, things are a bit different. You're never gonna make your own thread to block on things. You're gonna use Lwt to manage all your concurrency so you can do tons of blocking stuff at the same time and combine the tasks nicely without ending up in a Node.js-style "callback hell".
But still, even with tons of concurrency, you don't have parallelism. It's all you need for 98% of your programs, but if you then need to do heavy number-crunching it won't be enough. This is the exact same situation that happens in Node.js, Python, etc, except that OCaml is massively faster than those languages, so even some CPU-bound work is acceptable because OCaml is really performant.
Currently, there's 2 options if you wanna do CPU-bound work: you can use ctypes to call C code easily (from Lwt_preemptive) and then release the lock from within C with caml_release_runtime_system(), so your C code will be truly parallel (and running in the thread pool automatically managed by Lwt_preemptive), and you can call caml_acquire_runtime_system() before returning the result back to OCaml to get the lock back and merge back with the normal code.
The second option is to do an oldschool fork() and communicate with message-passing. Or have a master that manages workers and communicates with ZMQ, HTTP, TCP, IPC, etc. Or use a library that does it all for you like parmap, Async Parallel, etc etc.
What this "multicore support" means is that you'll be able to have threads in the same process that run in parallel because the GIL is going away. In practice it'll probably be implemented directly into Lwt so you'll be able to do something with Lwt_preemptive and just tell it to run some function in a separate thread and then use >>= to handle its result. It's gonna be simpler than both options I described above.
Again, more technical information is available in my r/ocaml post
The second option is to do an oldschool fork() and communicate with message-passing. Or have a master that manages workers and communicates with ZMQ, HTTP, TCP, IPC, etc. Or use a library that does it all for you like parmap, Async Parallel, etc etc.
I work on the Hack language typechecker at Facebook. The typechecker is written in OCaml, and since it needs to operate on the scale of Facebook's codebase (tens of millions of lines of code), it's a pretty performance-sensitive program. We needed real parallelism, but doing it with fork() and IPC was too costly for us, both in terms of storage (if you aren't careful you end up duplicating a bunch of data) and CPU (serializing/deserializing OCaml data structures to send over IPC is CPU-intensive).
We ended up doing something somewhat more interesting. Before we fork(), we mmap a MAP_ANON|MAP_SHARED region of memory -- that region will be backed by the same physical frames in each child after we fork, so writes to it in one child process will be visible in the others. We use a little bit of C code to safely manage the shared-memory concurrency here.
We ended up doing something somewhat more interesting. Before we fork(), we mmap a MAP_ANON|MAP_SHARED region of memory -- that region will be backed by the same physical frames in each child after we fork, so writes to it in one child process will be visible in the others. We use a little bit of C code to safely manage the shared-memory concurrency here.
Isn't that similar to how Linux implemented threads for a long time (before NPTL [1]) ?
I vaguely recall that for a long time people were complaining about the cost of starting threads in Linux, because it basically amounted to fork()+shared memory.
I don't know the history of threads/NPTL on Linux. However, the distinction between "thread" and "process" in the Linux kernel is mostly a human one, not a technical one. Take a look at the clone() syscall -- spawning a thread vs. forking a process amount just to different flags to that call, to tell it whether to copy pages or not, how to assign a new ID to the new thread/process, etc. (Not sure if that's how fork() and friends are actually implemented under the hood.)
When implementing fork(2), the return value from clone(2) is the child's PID from the context of the parent process. When implementing pthread_create(3), the return value for the parent is still an integer value which is unique to the thread, and which strace uses as if it were a PID when it's tracing down the system calls of individual threads in separate files, which strace can do because it's awesome.
Some more information:
Linux has a unique implementation of threads. To the Linux kernel, there is no concept of a thread. Linux implements all threads as standard processes. The Linux kernel does not provide any special scheduling semantics or data structures to represent threads. Instead, a thread is merely a process that shares certain resources with other processes. Each thread has a unique task_struct and appears to the kernel as a normal process (which just happens to share resources, such as an address space, with other processes).
Other languages that have a GIL (and the same restriction) are Javascript (including Node.js)
Not quite true; JS just doesn't support threads at all. It's asynchronous and single-threaded. In node.js's case, an event loop uses a system call like epoll or kqueue to wait for many events at a time, and dispatches those events to the correct callbacks.
You can do parallelism in JS with Web Workers, and they do use native OS threads, but they lack shared memory, and can only communicate using message passing. So from the perspective of the JS code, they behave more like processes than threads. No GIL, in any case.
I think thats not directly language related but an implementation detail - although a very important one. Javascript on the JVM (Nashorn) allows full multithreading - including then the need for all the common synchronization stuff.
But of course - Javascript and also the typical Javascript libraries were not made with multithreading in mind.
The thing is that numbers are usually wrapped in other things, like objects, hashtables, arrays, etc, and OCaml is a beast at dealing with that kind of code.
From a purely numbers perspective, its operations on integers have to use the LEA instruction instead of ADD (for example) because of the 1-bit tag, which slows things down a bit, but the speed at dealing with symblic code as I explained above more than makes up for it.
Comments
More information is available
in my original post in r/ocaml: https://www.reddit.com/r/ocaml/comments/36ninh/403_scheduled...
in the repost in r/programming: https://www.reddit.com/r/programming/comments/36ppx0/ocaml_4...
For those asking "How the hell does OCaml not support multicore in 2015????", this is my reply, crossposted from /r/ocaml:
You can make OS level threads, but they can't be both running at the same time due to the GIL (Global Interpreter Lock). Then why are they even there you might ask? Because it allows you to do a blocking call on a thread and to keep executing other stuff in the main thread. Other languages that have a GIL (and the same restriction) are Javascript (including Node.js), Ruby and Python.
Now, IN PRACTICE, things are a bit different. You're never gonna make your own thread to block on things. You're gonna use Lwt to manage all your concurrency so you can do tons of blocking stuff at the same time and combine the tasks nicely without ending up in a Node.js-style "callback hell".
But still, even with tons of concurrency, you don't have parallelism. It's all you need for 98% of your programs, but if you then need to do heavy number-crunching it won't be enough. This is the exact same situation that happens in Node.js, Python, etc, except that OCaml is massively faster than those languages, so even some CPU-bound work is acceptable because OCaml is really performant.
Currently, there's 2 options if you wanna do CPU-bound work: you can use ctypes to call C code easily (from Lwt_preemptive) and then release the lock from within C with caml_release_runtime_system(), so your C code will be truly parallel (and running in the thread pool automatically managed by Lwt_preemptive), and you can call caml_acquire_runtime_system() before returning the result back to OCaml to get the lock back and merge back with the normal code.
The second option is to do an oldschool fork() and communicate with message-passing. Or have a master that manages workers and communicates with ZMQ, HTTP, TCP, IPC, etc. Or use a library that does it all for you like parmap, Async Parallel, etc etc.
What this "multicore support" means is that you'll be able to have threads in the same process that run in parallel because the GIL is going away. In practice it'll probably be implemented directly into Lwt so you'll be able to do something with Lwt_preemptive and just tell it to run some function in a separate thread and then use >>= to handle its result. It's gonna be simpler than both options I described above.
Again, more technical information is available in my r/ocaml post
I work on the Hack language typechecker at Facebook. The typechecker is written in OCaml, and since it needs to operate on the scale of Facebook's codebase (tens of millions of lines of code), it's a pretty performance-sensitive program. We needed real parallelism, but doing it with fork() and IPC was too costly for us, both in terms of storage (if you aren't careful you end up duplicating a bunch of data) and CPU (serializing/deserializing OCaml data structures to send over IPC is CPU-intensive).
We ended up doing something somewhat more interesting. Before we fork(), we mmap a MAP_ANON|MAP_SHARED region of memory -- that region will be backed by the same physical frames in each child after we fork, so writes to it in one child process will be visible in the others. We use a little bit of C code to safely manage the shared-memory concurrency here.
The code for this all open source (along with the rest of the typechecker, HHVM runtime, etc) if you want to take a look: https://github.com/facebook/hhvm/blob/master/hphp/hack/src/h...
I also gave a tech talk a while ago on internals of the type system and typechecker; the latter part starts here: https://www.youtube.com/watch?v=aN22-V-b8RM&feature=youtu.be...
Isn't that similar to how Linux implemented threads for a long time (before NPTL [1]) ?
I vaguely recall that for a long time people were complaining about the cost of starting threads in Linux, because it basically amounted to fork()+shared memory.
[1] http://en.wikipedia.org/wiki/Native_POSIX_Thread_Library
I don't know the history of threads/NPTL on Linux. However, the distinction between "thread" and "process" in the Linux kernel is mostly a human one, not a technical one. Take a look at the clone() syscall -- spawning a thread vs. forking a process amount just to different flags to that call, to tell it whether to copy pages or not, how to assign a new ID to the new thread/process, etc. (Not sure if that's how fork() and friends are actually implemented under the hood.)
If you use strace you can see that it is. fork(2) and pthread_create(3) both show up as calls to clone(2).
Just for the edification of the masses:
pthread_create(3) looks something like this:
(Newlines are mine.)Of course, those pointers are only that size on a 64-bit architecture. The flags are where the real point of interest is.
fork(2) is like this:
When implementing fork(2), the return value from clone(2) is the child's PID from the context of the parent process. When implementing pthread_create(3), the return value for the parent is still an integer value which is unique to the thread, and which strace uses as if it were a PID when it's tracing down the system calls of individual threads in separate files, which strace can do because it's awesome.Some more information:
http://www.makelinux.net/books/lkd2/ch03lev1sec3
Not quite true; JS just doesn't support threads at all. It's asynchronous and single-threaded. In node.js's case, an event loop uses a system call like epoll or kqueue to wait for many events at a time, and dispatches those events to the correct callbacks.
You can do parallelism in JS with Web Workers, and they do use native OS threads, but they lack shared memory, and can only communicate using message passing. So from the perspective of the JS code, they behave more like processes than threads. No GIL, in any case.
I think thats not directly language related but an implementation detail - although a very important one. Javascript on the JVM (Nashorn) allows full multithreading - including then the need for all the common synchronization stuff.
But of course - Javascript and also the typical Javascript libraries were not made with multithreading in mind.
The numerical benchmark table in http://julialang.org/ suggests that JavaScript is quite a number crunching beast, within 2x-3x of C performance.
The thing is that numbers are usually wrapped in other things, like objects, hashtables, arrays, etc, and OCaml is a beast at dealing with that kind of code.
From a purely numbers perspective, its operations on integers have to use the LEA instruction instead of ADD (for example) because of the 1-bit tag, which slows things down a bit, but the speed at dealing with symblic code as I explained above more than makes up for it.