--- Log opened Thu Apr 24 00:00:45 2008 |
01:14 | | You're now known as TheWatcher[T-2] |
01:17 | | You're now known as TheWatcher[zZzZ] |
01:52 | | gnolam [lenin@Nightstar-10613.8.5.253.static.se.wasadata.net] has quit [Quit: Z?] |
05:05 | | AnnoDomini [AnnoDomini@Nightstar-29755.neoplus.adsl.tpnet.pl] has joined #Code |
05:05 | | mode/#code [+o AnnoDomini] by ChanServ |
05:24 | | Vornicus-Latens is now known as Vornicus |
06:38 | | Vornotron [~vorn@Admin.Nightstar.Net] has joined #code |
06:39 | | Vornicus [~vorn@Admin.Nightstar.Net] has quit [Ping Timeout] |
06:41 | | Vornotron is now known as Vornicus |
07:26 | | Shoukanjuu [~Shoukanju@67.232.205.ns-21904] has quit [Ping Timeout] |
07:33 | | Shoukanjuu [~Shoukanju@67.232.178.ns-12163] has joined #code |
09:30 | | You're now known as TheWatcher |
10:08 | | AnnoDomini [AnnoDomini@Nightstar-29755.neoplus.adsl.tpnet.pl] has quit [Ping Timeout] |
10:13 | | AnnoDomini [AnnoDomini@Nightstar-29144.neoplus.adsl.tpnet.pl] has joined #Code |
10:13 | | mode/#code [+o AnnoDomini] by ChanServ |
10:56 | < Jeff> | Does anyone here understand the differences between a condition variable and semaphores? |
10:56 | < Jeff> | Fuck, are there differenceS? |
10:57 | <@McMartin> | They are entirely separate constructs with no shared primitives. |
10:57 | <@McMartin> | The short answer, however, is that condition variables will Fuck You Up Good. |
10:57 | <@McMartin> | They are *much* harder to use right. |
10:58 | < Jeff> | Could you explain how their wait() and signal() ops differ? |
10:58 | <@McMartin> | I am preparing an example now. |
10:58 | < Jeff> | Because the notes I have are... unhelpful. |
10:58 | <@McMartin> | Here's the difference. We'll have two threads, A and B. A is supposed to do something, then signal B to indicate that it's done. |
10:58 | <@McMartin> | Here's one thread interleaving. |
10:59 | <@McMartin> | B.wait(); A.doSomething(); A.signal(); |
10:59 | <@McMartin> | That one works for both. |
10:59 | <@McMartin> | Here's another. |
10:59 | <@McMartin> | A.doSomething(); A.signal(); B.wait(); |
10:59 | <@McMartin> | That one is fine for semaphores -- its value goes positive so that when B waits it immediately returns -- but it is a deadlock for condition variables. |
10:59 | <@McMartin> | A's signal is lost to the ether and B waits forever for an event that will never occur again. |
11:00 | <@McMartin> | In order to use CVs safely, they *must* be combined with mutexes, like so: |
11:01 | <@McMartin> | B.lock(l); B.wait(l) -- which *atomically* unlocks the mutex and begins the wait - otherwise A can sneak in with a signal that will be lost... |
11:01 | <@McMartin> | A.doSomething(); A.lock(l); A.signal(); A.unlock(l); |
11:01 | <@McMartin> | B.unlock(l). |
11:02 | <@McMartin> | Oh, and in order for this to be safe B has to ensure that A can't start until after it's acquired lock l in the first place. |
11:02 | <@McMartin> | So, I hear you ask, why the fuck would anyone ever use condition variables in the first place. |
11:02 | <@McMartin> | I'm glad you asked! That's an excellent question. |
11:02 | < Jeff> | You don't have an answer, do you? |
11:02 | <@McMartin> | It's because in addition to wait() and signal(), CVs also allow broadcast(), which signals everyone waiting on it, not just one. |
11:02 | <@McMartin> | This capability cannot be gotten directly with semaphores. |
11:03 | <@McMartin> | (The locking mechanism - and the fact that to truly wake up, you must also acquire the lock - keep the freshly awakened threads from stomping all over one another.) |
11:04 | <@McMartin> | All of that said, every synchronization primitive is at some level equivalent; mutexes, recursive mutexes, semaphores, critical sections, and condition variables are all implementable in terms of the others. |
11:04 | < Jeff> | To be completely honest, I never exactly understood anything after spinlocks. |
11:04 | <@McMartin> | But CVs require mutexes as part of their structure, so you might as well also break them out. |
11:05 | <@McMartin> | Spinlocks are one way of implementing mutex. |
11:05 | < Jeff> | The prof talked about building higher-level locks from "spinlock primitives" and didn't go into details. |
11:05 | < Jeff> | It seems to me that if you build a higher-level lock out of a spinlock, you have higher-level spinlocks. |
11:05 | <@McMartin> | Generally, if you have a proper OS, you only use spinlocks at the absolute lowest level and instead put the thread to sleep anywhere else. |
11:06 | <@McMartin> | Which is *not* spinlocking since using a spinlock consumes all your CPU. |
11:06 | < Jeff> | Right. Which is, even I can tell, A Bad Thing. |
11:06 | < Jeff> | Almost as bad as losing your hat. |
11:07 | <@McMartin> | Right. So basically you use the spinlocks inside the OS to talk to the hardware, and everywhere else when you *would* spin you instead sleep until the OS decides to let you try again, giving your cycles to someone else. |
11:07 | <@McMartin> | The nice thing about CVs is that they directly implement the concept of "sleeping now. Wake me up when you're ready" |
11:08 | <@McMartin> | To implement a reentrant mutex, you use a simple mutex to protect a chunk of data that indicates (a) who owns it, as per a simple mutex, and (b) how many times they've locked it. |
11:08 | <@McMartin> | And then you don't *actually* unlock it until that count goes back to zero. |
11:08 | < Jeff> | Just to make sure I've got it right- |
11:08 | < Jeff> | If, in a condition variable, a wait() command is called after the last signal() command, the thread will wait forever. |
11:08 | < Jeff> | Yes? |
11:08 | <@McMartin> | Yes. And we're pretending broadcast() doesn't exist. |
11:09 | <@McMartin> | (The one place I've used CVs For Real was in a rendering engine where the renderer would broadcast() when it was out of work to do; this was a signal that slowdown due to rendering was no longer happening and it would start feeding the renderer commands again) |
11:09 | <@McMartin> | There's nothing stopping some main loop somewhere from just signalling the variable periodically just to make sure nobody's wedged. |
11:09 | | Chalcedon [~Chalcy@Nightstar-488.ue.woosh.co.nz] has quit [Quit: Leaving] |
11:09 | < Jeff> | Therefore, you need a locking mechanism around your wait() command to prevent it from... what? |
11:10 | <@McMartin> | Basically, you have to ensure that whoever was going to signal you doesn't get a chance to do it until after you've started to wait. |
11:10 | <@McMartin> | The classic example is that you're spinning off a subprocess and you're just going to sit and wait for the result. |
11:10 | <@McMartin> | That goes |
11:10 | < Jeff> | Semaphores, allowing you to progress through wait() when there are no other threads using the mutually exclusive code, simply bypass this, correct? |
11:10 | <@McMartin> | Parent gets lock |
11:11 | <@McMartin> | ... sort of. I think of semaphores as "buffering up unlocks" that can then be cashed in later. |
11:11 | <@McMartin> | It's legal to signal a semaphore that nobody's waiting on; if you do, then the next wait terminates immediately and the one after *that* is the one that blocks. |
11:12 | <@McMartin> | Anyway, classic Condition Variable comes from that rendering engine again. One of the commands is "wake me up once you've actually drawn everything I've asked for", to do animation as fast as the CPU allows, but with slowdown if it can't handle it. |
11:12 | <@McMartin> | That goes like this: |
11:12 | <@McMartin> | The threads are Game (G) and Renderer (R). The lock is L. |
11:13 | <@McMartin> | G locks L. |
11:13 | <@McMartin> | G enqueues a "wake me up" command on R's list. |
11:13 | <@McMartin> | Suddenly, the OS feels perverse and gives R as much time as it wants. |
11:13 | <@McMartin> | R empties its queue, and hits the wake me up command. |
11:13 | <@McMartin> | R prepares to signal G even though G hasn't waited yet. |
11:13 | <@McMartin> | In preparing, it locks L, or tries to. |
11:14 | <@McMartin> | This puts it to sleep, since G holds L. |
11:14 | <@McMartin> | Now G is the only runnable thread, and starts up. |
11:14 | < Jeff> | Okay. |
11:14 | <@McMartin> | G hits its wait() call. |
11:14 | < Jeff> | You seem to know a fair bit about threads. |
11:14 | <@McMartin> | G *simultaneously* unlocks L and goes to sleep. |
11:14 | <@McMartin> | It can't be interrupted between the unlock and the sleep, and this needs to be supported at the lowest levels. |
11:14 | <@McMartin> | Now R can get its lock and go. |
11:15 | <@McMartin> | It now hits signal(). G wakes up and tries to grab L, but can't since R has it. |
11:15 | <@McMartin> | R does whatever cleanup it would need to do to let G be consistent, which in this case is nothing. |
11:15 | <@McMartin> | So R just unlocks L, and we've had our transaction. |
11:16 | <@McMartin> | And yeah, I was directly responsible for changing the multithreaded code in The Ur-Quan Masters from the 3DO's thread model to the POSIX/pthreads/SDL model, which was somewhat different. |
11:16 | < Jeff> | Really, now? |
11:16 | <@McMartin> | Indeed. |
11:16 | <@McMartin> | (In particular, 3DO's were fire-and-forget, which pthreads supports but SDL does not, and they allowed asynchronous threadkills, which have since been decided to be Fundamentally A Bad Idea.) |
11:17 | <@McMartin> | Oh, right. |
11:17 | <@McMartin> | The other reason to use Condition Variables instead of Semaphores is if you're writing code in an older version of Java, CVs are the only decently powerful synchronization primitive that's implemented for you in the library. |
11:17 | <@McMartin> | As of 1.5 you get the whole set, I think. |
11:18 | < Jeff> | Got it. |
11:18 | <@McMartin> | (If this is for personal edification instead of for some class, I strongly recommend the Java book "Concurrent Programming in Java", which gives recipes for how to do most things directly.) |
11:19 | <@McMartin> | (Though given the price of such books you may want to instead find it in a library) |
11:19 | < Jeff> | (I'm afraid this is for a class. Am I a bad person for being confused by all this, and perhaps wondering if OS programming is Not For Me?) |
11:19 | <@McMartin> | (The usual metric is that systems-level programming of this nature is nine times harder than regular applications programming) |
11:20 | < Jeff> | *hiss* Nine times? |
11:20 | <@McMartin> | (two factors of 3x; one for having to cope with *everything*, and one for being persnickety to get right even in ideal cases) |
11:20 | < Jeff> | No wonder this is a class everyone puts off. |
11:20 | <@McMartin> | (And this is pulled out of some studies of productivity from, like, the late 60s, so you know, grain of salt etc) |
11:20 | < Jeff> | (Too bad it's a prereq for a lot of interesting-looking stuff.) |
11:20 | <@McMartin> | (But it feels about right to me) |
11:20 | <@McMartin> | Yeah, Systems is pretty core. |
11:21 | <@McMartin> | You absolutely have to have at least the basics if you want a chance at dealing with anything much more complicated than an IRC client, since pretty much all programs have to be at least a little concurrent. |
11:21 | <@McMartin> | Or the OS will be *making* it concurrent on you behind the scenes (GUI programs tend to fabricate their own event handler threads, etc) |
11:22 | < Jeff> | (Right.) |
11:22 | <@McMartin> | The rest of OS stuff is good background |
11:22 | < Jeff> | Remind me, why do we even mess with multiple threads? I mean, before last quarter I never really messed with the "thread" options. |
11:22 | < Jeff> | I assumed they were relatively obscure because I had never seen them before. Stupid, I know, but... |
11:22 | <@McMartin> | Concurrency is easily the Hardest Problem People Regularly Have To Deal With, though, and I don't consider it solved. |
11:22 | <@McMartin> | Well |
11:23 | <@McMartin> | You've got processes, which need to communicate, etc. |
11:23 | <@McMartin> | UNIX handles this by treating everything like a file or an input stream, and this turns out to be pretty awesome. |
11:23 | <@McMartin> | The difference between a thread and a process is that threads share all their memory |
11:23 | < Jeff> | Right, I know that. |
11:24 | <@McMartin> | The reason you want this is because it's much easier to write a program with multiple threads of control than to attempt to ensure that every thing that needs to be done simultaneously periodically hands off its control to someone else. |
11:24 | < Jeff> | It seems to me that "anything you can do with multithreads you can do with one single thread" though I suppose that's like saying "anything you can do in a compiled language you can do in a Turing Machine". |
11:24 | <@McMartin> | It is like that, yes. |
11:24 | <@McMartin> | The big blaring case for this is that if you're in the middle of some huge computation, you still want the user to be able to move the window around. |
11:25 | <@McMartin> | And without threads your huge computation has to occasionally go and handle window events. |
11:25 | <@McMartin> | And this sucks. |
11:25 | <@McMartin> | (It is, however, faster, so it's what you do at the lowest level when you're actually writing the windowing system. But you don't want someone putting a semicolon in the wrong place to wedge the whole desktop, so you want to have the threads be pre-emptible by the OS.) |
11:26 | < Jeff> | (Yes.) |
11:26 | < Jeff> | Okay. I suppose I understand the need for this in the abstract. But ... how shall I put this... how often will the code I'm writing have to Deal With concurrency? |
11:26 | <@McMartin> | Depends on what you're writing, really. |
11:27 | <@McMartin> | GUI apps, it's minimal and mainly just involves making sure that you aren't doing too much work in the event-processing thread |
11:27 | <@McMartin> | As an example, a GUI app I've been working on recently used to have a button that, when you pushed it, initiated a humongous directory scan. |
11:27 | < Jeff> | Let's say I haven't been completely broken yet and still harbor fantasies of working on games someday. |
11:27 | < Jeff> | ...that's gonna need threads, yeah. |
11:27 | <@McMartin> | This was a Big Mistake, so I put the scan in its own thread and then life was good. |
11:28 | <@McMartin> | But that was basically "new Thread() { void run() { ... code here ... } }.run();" |
11:28 | <@McMartin> | Er. |
11:28 | <@McMartin> | .start();. |
11:28 | <@McMartin> | And then there's another magic function in Swing to send another chunk of code back to be run in the Event thread when I was done (to update the GUI with the results of the scan). |
11:29 | <@McMartin> | So that kind of thing is going to be basically unavoidable |
11:29 | <@McMartin> | And if you're messing with global variables, you're going to have to concern yourself with locking to ensure that if the user starts two scans at once there is no damage. |
11:29 | <@McMartin> | I dealt with it by ensure that each scan only touched thread-local storage. |
11:30 | <@McMartin> | If you can prove that, then you don't need locks at all. |
11:30 | <@McMartin> | Asynchronous network protocols tend to be threaded; you have a thread that listens and that makes things happen when the world gives it input |
11:31 | <@McMartin> | Massive Parallelism hasn't shown up much. |
11:31 | <@McMartin> | Yet. |
11:31 | <@McMartin> | Outside of things like pixel shaders |
11:31 | <@McMartin> | But it's been The Technology Of The Future for almost 10 years now, and consumer products are starting to seriously deploy it. |
11:31 | <@McMartin> | We're going to have to learn, but we haven't yet, and once we do, it's not going to look recognizable. |
11:32 | <@McMartin> | You'll usually have to be vaguely aware that other users exist, at this point, but that's all you really have to care about. |
11:32 | <@McMartin> | Web applications tend to be wildly multithreaded, but you write them as if any given user is the only being in the world until you have to touch a database or something. |
11:33 | <@McMartin> | My graduate thesis prototype wasn't multithreaded, but it (as a program monitor) had to be able to operate properly in the presence of multithreaded programs. |
11:34 | <@McMartin> | UQM used to have way too many threads but I and the rest of coredev pared it down to "main thread", "rendering thread", "sound decoding/playback thread", and "ambient animation thread", basically. |
11:34 | <@McMartin> | Which is another case where you've got stuff that you want Continuously Happening that you don't want the rest of the code to have to think about. |
11:34 | <@McMartin> | So yeah, for what it's worth. |
11:35 | <@McMartin> | And now, it's way too late, so I'm going to bed. Good luck on your project. |
11:35 | | You're now known as TheWatcher[afk] |
11:36 | < Jeff> | Night. |
11:36 | < Jeff> | One more problem. |
11:37 | < Jeff> | *eyerub* |
11:44 | | gnolam [lenin@Nightstar-10613.8.5.253.static.se.wasadata.net] has joined #Code |
11:45 | | mode/#code [+o gnolam] by ChanServ |
12:18 | | You're now known as TheWatcher |
14:29 | | DiceBot [~Reiver@Nightstar-11590.xdsl.xnet.co.nz] has joined #Code |
15:37 | | Vornicus [~vorn@Admin.Nightstar.Net] has quit [Ping Timeout] |
15:37 | | Vornotron [~vorn@Admin.Nightstar.Net] has joined #code |
15:37 | | Vornotron is now known as Vornicus |
16:20 | <@ToxicFrog> | Re "anything you can do with multithreads you can do with one single thread" - |
16:21 | <@ToxicFrog> | With the increasing popularity of SMP machines, this is no longer the case, and there are programs - albeit still in the minority - that use threads not for organizational purposes, but so that they can spread heavy computation across multiple cores and get improved performance thereby. |
16:29 | <@McMartin> | That makes it a performance hack |
17:01 | | Jeff [~JPL@Nightstar-509.dsl.sndg02.pacbell.net] has quit [Ping Timeout] |
17:02 | | JeffL [~JPL@Nightstar-12594.dsl.sndg02.pacbell.net] has joined #code |
17:05 | <@Kazriko> | Other than performance, there was never much reason to use multithreading, even with a single core. You want your program to respond quickly to both keyboard and network traffic? otherwise, a single thread is fine. heh |
17:05 | <@McMartin> | Kazriko: For processing of multiple simultaneous requests, you get (imo) a significantly cleaner software architecture with multithreading as well. |
17:05 | | Jeff [~JPL@Nightstar-12594.dsl.sndg02.pacbell.net] has joined #code |
17:06 | <@Kazriko> | But multi threads definitely help with performance |
17:06 | | JeffL [~JPL@Nightstar-12594.dsl.sndg02.pacbell.net] has quit [Ping Timeout] |
17:06 | <@Kazriko> | Well, there are other ways of getting that as well. Asyncore in python is one way that makes it look as clean as a multithreaded program. |
17:07 | <@McMartin> | Presumably it does this by sneaking in taskswitch calls somewhere? |
17:08 | <@Kazriko> | It only handles the network part, but can handle multiple network connections at once on a single thread. |
17:08 | | You're now known as TheWatcher[afk] |
17:08 | <@Kazriko> | then it can dispatch the incoming network calls to separate objects. |
17:09 | <@McMartin> | Aha |
17:09 | <@McMartin> | Upon further contemplation I've decided that decoding an MP3 file or whatnot in background and shoving it at the soundcard is actually the ultimate "be MT, it's just easier" application. |
17:10 | <@Kazriko> | The only downside is that you don't want to do anything time intensive in those objects, as it blocks other incoming until you've returned. |
17:10 | <@McMartin> | Quite. |
17:10 | <@McMartin> | That's where I was going originally, last night. |
17:10 | <@McMartin> | The "short thing" you do is spawn a thread to do the real work. |
17:11 | <@Kazriko> | what Ennesbot 0.5 will do is have a very thin handler attached between each bot and Asyncore, but at the end shove it into a queue for a dispatch thread that is separate for each connection. |
17:12 | <@Kazriko> | It handles pings, and a couple others directly (anything that is timing critical) |
17:12 | <@Kazriko> | but anything else is handled by the other thread. :) |
17:14 | <@Kazriko> | We used to have 2 threads for each network connection, one whose sole job was sucking data out of the socket and sending data to it, the other that would execute all of the plugins that want that message. |
17:15 | <@Kazriko> | Now if there's anything that takes more than a second, then they still want to spawn another thread for it. We have a dedicated timer thread too, and we have code for spawning a thread to handle a sql query. :) |
17:17 | <@Kazriko> | ok, time to head to work. |
18:33 | | You're now known as TheWatcher |
19:47 | | C_tiger [~c_wyz@Nightstar-26295.nycmny.east.verizon.net] has quit [Connection reset by peer] |
19:49 | | C_tiger [~c_wyz@Nightstar-5214.nycmny.east.verizon.net] has joined #code |
19:49 | | mode/#code [+o C_tiger] by ChanServ |
20:17 | | C_tiger [~c_wyz@Nightstar-5214.nycmny.east.verizon.net] has quit [Quit: And away she goes!] |
20:26 | | C_tiger [~c_wyz@Nightstar-5214.nycmny.east.verizon.net] has joined #code |
20:26 | | mode/#code [+o C_tiger] by ChanServ |
20:37 | | C_tiger [~c_wyz@Nightstar-5214.nycmny.east.verizon.net] has quit [Quit: And away she goes!] |
20:40 | | Vornicus [~vorn@Admin.Nightstar.Net] has quit [Ping Timeout] |
21:23 | | Chalcedon [~Chalcy@Nightstar-488.ue.woosh.co.nz] has joined #code |
21:23 | | mode/#code [+o Chalcedon] by ChanServ |
21:40 | | Serah [~Z@87.72.35.ns-26506] has quit [Connection reset by peer] |
22:10 | | ASCIISkull [~none@Nightstar-7066.dyn.optonline.net] has joined #code |
22:10 | | AFKSkull [~none@Nightstar-7066.dyn.optonline.net] has quit [Ping Timeout] |
22:11 | | ASCIISkull is now known as NSGuest-6247 |
22:11 | | NSGuest-6247 is now known as AFKSkull |
23:06 | | AnnoDomini [AnnoDomini@Nightstar-29144.neoplus.adsl.tpnet.pl] has quit [Quit: Faerie gold... it is always illusion in the end.] |
23:11 | | Jeff [~JPL@Nightstar-12594.dsl.sndg02.pacbell.net] has quit [Quit: Leaving] |
23:29 | | NSGuest-6249 [~Z@87.72.35.ns-26506] has joined #Code |
--- Log closed Fri Apr 25 00:00:51 2008 |