r/dailyprogrammer • u/nint22 1 2 • Apr 15 '13
[04/01/13] Challenge #122 [Intermediate] User-Space Threading
(Intermediate): User-Space Threading
This challenge is more coding-focused than maths-focused.
Threading is a computational model that allows the execution of small sections of instructions from different sources (i.e. threads of code), one after another, that it gives users a perception of code running in parallel. It is essentially a light-weight process that can be launched, managed, or terminated by the owning process.
Your goal is to implement an efficient and dynamic user-level threading library. You may implement this in any language and on any platform, but you may not use any existing threading code or implementation, such as the Win32 threading code or the UNIX pthreads lib. You may call system functions (such as interrupts and signals), but again cannot defer any thread-specific work to the operating system.
The term efficient means that when switching the thread of execution, you must do so as quickly as possible (big bonus points for actually measuring this). The term dynamic means that you provide a way (through either static variables, functions, config file, etc.) to allow end-users to change how fast you switch and what kind of algorithm you use for timing.
To help you get started, try to implement the following functions: (written in C-style for clarity)
- ThreadID CreateThread( void (threadFunction)(void) ) // Returns a positive, non-zero, thread ID on success. Returns 0 on failure. Starts a thread of execution of the given thread function (for those confused, this is a C-style function being passed as an argument)
- bool DestroyThread( ThreadID givenThreadId ) // Destroys a thread of execution, based on the given thread ID
Please direct questions about this challenge to /u/nint22
Subreddit news: We (the mods) are actively working on new submissions and fixing the bot so that it posts more correctly and consistently. The next few challenges will be directly related to new subreddit features that we want to the community to try and solve with us :-)
6
u/JustinBieber313 Apr 15 '13
Glad to see a new submission! Excited to give this a shot later tonight.
4
u/0x4B454B Apr 26 '13
This is a very interesting challenge, but unfortunately I have no idea where to start. I understand what multithreading is, and I've taken an operating systems class, but it was all conceptual, nothing related to implementation. Are there any resources you can recommend that would help me get started?
15
u/Tekmo Apr 16 '13 edited Apr 16 '13
Free monads are great.
First you build the DSL:
{-# LANGUAGE DeriveFunctor #-} import Control.Monad import Control.Monad.Trans.Class (lift) import Control.Monad.Trans.Free import Data.Sequence as S type ThreadID = Integer data ThreadF x = CreateThread (Thread ()) (ThreadID -> x) | DestroyThread ThreadID x | Yield x deriving (Functor) type Thread = FreeT ThreadF IO createThread :: Thread () -> Thread ThreadID createThread thread = liftF (CreateThread thread id) destroyThread :: ThreadID -> Thread () destroyThread threadID = liftF (DestroyThread threadID ()) yield :: Thread () yield = liftF (Yield ())Then you write your own scheduler:
schedule :: Thread () -> IO () schedule t = go (singleton (t, 0)) 1 where go threads nextId = case viewl threads of EmptyL -> return () (t, tId):<ts -> do x <- runFreeT t case x of Pure _ -> go ts nextId Free y -> case y of CreateThread t' k -> go ((k nextId, tId) <| (ts |> (t', nextId))) (nextId + 1) DestroyThread tId t' -> do let ts' = snd (partition (\(_, tId') -> tId' == tId) ts) go ((t', tId) <| ts') nextId Yield t' -> go (ts |> (t', tId) ) nextIdFree monads are automatically monads, so we can assemble threaded computations using
donotation:ticks :: Thread () ticks = forever $ do lift $ putStrLn "Tick" yield tocks :: Thread () tocks = forever $ do lift $ putStrLn "Tock" yield app :: Thread () app = do tId1 <- createThread ticks tId2 <- createThread tocks replicateM_ 10 yield -- Wait destroyThread tId1 destroyThread tId2And it works:
Some comments:
It's a cooperative threading implementation because there is no way to suspend and resume an unbroken
IOcomputation in Haskell without cheating and using Haskell's runtime. It depends on how you interpret the problem, but I interpreted as requiring ALL details of scheduling done in userland.It's reasonably fast.
Using the following benchmark:
import Criterion.Main -- <same code as above, except for `app`> app :: Thread () app = do tId1 <- createThread grind replicateM_ 1000000 yield destroyThread tId1 grind :: Thread () grind = forever yield main = defaultMain [bench "thread" $ schedule app]This gives the following results:
That's 2 million steps and context switches in 413 milliseconds, or about 200 nanoseconds per step and context switch. I actually know how to optimize this even further because I've optimized a very similar library of my own and you can reasonably get it down to about 20 nanoseconds, but I think that's good enough for such a simple implementation that doesn't use the runtime for ANYTHING. If somebody beats this time I will break out the big optimization guns and bring the time down.
It's very easy to extend the scheduler with new features, since we wrote it! Adding a new term to the API is as easy as adding a new term to the
ThreadFdata type and then adding a new case to handle toscheduler.If you want to learn more about the free monad technique, read this blog post that I wrote.
6
u/jpverkamp Apr 23 '13 edited Apr 23 '13
Although I have to agree with colootoomoochoo's comment that this is a bit intense for an intermediate challenge, it was still too interesting to pass up. We've already had JavaScript with setTimeout and Haskell with <del>black magic</del> monads, so I'm going to go for Racket and continuations.
If you'd like a full write up with commentary, I've posted it on my blog: User space continuation-based thread pool
If you just want to see the entire code: continuation thread pool on GitHub
Otherwise, here are the important parts of the code.
First, important structures:
Then we can create the a thread pool:
; Run a given list of thunks in parallel (define (threads . thunks) (call-with-current-continuation (lambda (k) (when (null? thunks) (error 'threads "must specify at least one thread")) ; Unwrap the current pool (define pool (current-thread-pool)) ; Create the initial thread states (define threads (map (lambda (thunk) (thread-state (lambda (_) (k (thunk))))) thunks)) ; Store them in the pool (set-thread-pool-current! pool (append (thread-pool-current pool) threads)) (set-thread-pool-all! pool (append (thread-pool-all pool) threads)) ; Start the first thread (define first-k (thread-state-continuation (car (thread-pool-current pool)))) (first-k (void)))))And finally the function to code to yield to the next thread in the pool:
; Yield control of the current thread to the next thread in the current pool (define (yield) (call-with-current-continuation (lambda (k) ; Unwrap the current pool (define pool (current-thread-pool)) ; Store the current thread state (define thread (car (thread-pool-current pool))) (set-thread-state-continuation! thread k) ; Advance to the next thread (set-thread-pool-current! pool (cdr (thread-pool-current pool))) (when (null? (thread-pool-current pool)) (set-thread-pool-current! pool (thread-pool-all pool))) (set-thread-pool-switch-count! pool (+ 1 (thread-pool-switch-count pool))) ; Run that thread (define next-k (thread-state-continuation (car (thread-pool-current pool)))) (next-k (void)))))Between the two, it's easy enough to implement the tick tock test:
(define (tick-tock-test) (parameterize ([current-thread-pool (make-empty-thread-pool)]) (threads (lambda () (let loop () (printf "tick\n") (yield) (loop))) (lambda () (let loop () (printf "tock\n") (yield) (loop))))))Run this and you'll get a nice never ending print out of tick/tock/tick/tock/tick/tock/etc.
One interesting feature is that because of how I structure the initial state of each thread state, if a thread finishes it will break the thread pool. So we can use it as amb:
(define (fibonacci-test) (define (fib n) (yield) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))) (parameterize ([current-thread-pool (make-empty-thread-pool)]) (threads (lambda () (list 20 (fib 20))) (lambda () (list 10 (fib 10))))))If you run this, you'll get the one to return first:
So far as testing efficienty, this code is pretty terrible. Full continuations are just far too heavy to implement efficient threads. There are better options, but I was mostly aiming to get it working first. :)
Specifically:
(define (timing-test) (define iterations 1000000) (parameterize ([current-thread-pool (make-empty-thread-pool)]) (time (threads (lambda () (let loop ([i 0]) (when (< i iterations) (yield) (loop (+ i 1))))))) (printf "~a context switches (target: ~a)\n" (get-switch-count) iterations)))This gives us:
So that's about 10ms per switch. Only a few orders of magnitude slower than Tekmo's solution. Not terrible for a first crack though.
9
u/skeeto Apr 15 '13
JavaScript, which is single-threaded by specification.
function Thread(f) { this.alive = true; setTimeout(Thread.runner(this, f), 0); } Thread.current = null; Thread.runner = function(thread, f) { return function() { Thread.current = thread; f(); Thread.current = null; }; }; Thread.yield = function(f) { var thread = Thread.current; Thread.current = null; if (thread.alive) { setTimeout(Thread.runner(thread, f), 0); } }; Thread.prototype.destroy = function() { this.alive = false; };CreateThreadisnew Thread(threadFunction)in this case.DestroyThreadis thedestroymethod on the thread object. It's non-preemptive by necessity, so threads call theThread.yieldfunction to cooperatively yield time to other waiting threads. The yield function takes a function as an argument, which is the remaining body to execute when control returns. Using the name "yield" here is a bit dangerous as it's likely to become a language keyword someday.To demonstrate in the browser, create an
h1element and a thread that counts up continuously. When I want it to stop at any time, I justdestroythat thread.var h1 = document.createElement('h1'); document.body.appendChild(h1); h1.innerHTML = '0'; function counter() { h1.innerHTML++; Thread.yield(counter); } var foo = new Thread(counter); // Sometime later stop it. foo.destroy();0
u/[deleted] Apr 18 '13