Sketchpad

posted on 2007-09-12 18:34:12

I was watching an interesting video this morning and had some thoughts I jotted down before class. I am reproducing them in their full, unsubstantiated, and provocative/controversial nature here. Later perhaps they will contribute to something a bit more formal. Note: The video features Simon Peyton-Jones talking about programming language evolution somewhat generally. I'd much rather him speak more about that stuff than the Haskell/STM talks he gave at OSCON. Hmm.

I promise I'll post something less disjointed and more intelligible/coherent/formal than this in the near future.

Notes:
Referencing Upcoming Radical Visions Essay, Trend A: Moving Away From X86
Facet 1) Hardware.

I'm sick of people poo-pooing the "concurrency crisis". To be fair, concurrency is the straw breaking the camel's back. To maintain sustainable growth in the computer industry we're having to do, as always, radical things on the hardware side. Not as always, however, is the fact that they're forcing lots of change in software/CS at the same time.

Is Erlang brilliant? Maybe. Is Erlang fortuitous? Certainly. It is probably the best option for the concurrency problem at hand. I'm not convinced that Scala or F# compare. Or Haskell for that matter. Haskell is a different sort of win.

We need concurrency more than controlled effects through a type system at present. The need for Haskell is still further out. Still less urgent.

^That's it. We're having two different conversations trying to discuss what the more urgent issue is. It's not Erlang vs. Haskell. It's concurrency vs. limited effects.

But what of (insert professor/coder name here)? What of those that are uninformed? Hell, what about (insert coder name here). What will they do when their code is sitting around not scaling to available resources?

Tertiary snippets:
Syntax is not semantics. Can we mistake it for such? Of course, but what does that look like? What is it to mistake syntax for semantics?

"That boy, does he already suspect that beauty is always elsewhere and always delusive?" - Czeslaw Milosz, New and Collected Poems, p. 284

The State of State

posted on 2007-08-29 13:20:44

So, I've been having and alluding to discussions with Tim Sweeney of late. I sent him an e-mail a little over two weeks back and I received word back from him about a week ago. It's taken a while for me to digest it a little and ask his permission to post it here but he has been kind enough to grant said permission. So, without further ado, the transcript:

Me:

Tim,

My name is Brit Butler. I'm a college student in Atlanta, GA and an admirer of your work. I was very taken with your POPL talk on The Concurrency Problem but curious as to why you mentioned both the message passing model and referentially transparent functions but then went on to mostly talk about the latter with Haskell. I'm certain that you've used and read about Erlang and other message-passing systems and was wondering if you could explain your position on them to me, vis-a-vis Transactional Memory or some other method. I'm assuming you wouldn't be in support of STM because it's ultimately still about sharing state. Thanks so much for your time.

Regards,
Brit Butler
http://www.redlinernotes.com/


Tim:
Hi,

Lots of applications and reasonable programming styles rely on large amounts of mutable state. A game is a great example – there are 1000’s of objects moving around and interacting in the world, changing each frame at 60 frames per second. We need to be able to scale code involving that kind of mutable state to threads, without introducing significant new programming burdens. Transactional memory is the least invasive solution, as it allows writing pieces of code which are guaranteed to execute atomically (thus being guaranteed of not seeing inconsistencies in state), using a fairly traditional style, and it scales well to lots of threads in the case where transactions seldom overlap and touch the same state.

Message-passing concurrency isn’t a very good paradigm for problems like this, because we often need to update a group of objects simultaneously, preserving atomicity. For example, within one transaction, the player object might decide to shoot, issue a command to his weapon, check an ammunition object, remove ammunition from it, and spawn a new bullet that’s now flying through the world. And the sets of objects which may need to atomically interact isn’t statically known – any objects that come into contact, or communicate, or are visible to each other, may potentially interact.

When implementing that kind of code on top of a message-passing concurrency layer, you tend to get bogged down writing numerous message interchanges which really just turn out to be ad-hoc transaction protocols. That’s quite error-prone. Better to just use transactions in that case.

This argument for transactional memory is limited in scope:

For algorithms which can be made free of side effects, pure functional programming (or “nearly pure functional programming” as in Haskell+ST) is cleaner and allows more automatic scaling to lots of threads, without committing to a particular granularity as with message-passing.

For algorithms that need to scale to multiple PCs, run across the Internet, etc, transactions seem unlikely to be practical. For in-memory transactions on a single CPU, the overhead of transactions can be brought down to <2X in reasonable cases. Across the network, where latencies are 1,000,000 times higher, message passing seem like the only plausible approach. This constrains algorithms a lot more than transactions, but, hey, those kinds of latencies are way too high to “abstract away”.

The existing Unreal engine actually uses a network-based message passing concurrency model for coordinating objects between clients and servers in multiplayer gameplay. It even has a nifty data-replication model on top, to keep objects in sync on both sides, with distributed control over their actions. It’s quite cool, but it’s inherently tricky and would add an awful lot of complexity if we used that for coordinating multiple threads on a single PC.

-Tim


So, there you have it. More on all this later. I've got to go play around with Erlang a bit more. I'm hoping Andre Pang and Patrick Logan will help me dig into this a bit deeper in days to come. Who else wants in on the conversation? Comment below.

Nerd Out

posted on 2007-08-17 12:27:58

So, I apparently asked a good question on Patrick Logan's blog. And he gave me a good answer:

"I can see someone making the argument in some domain I don't usually work in that shared memory threads are better than shared nothing message passing for performance reasons. Some hard-real time scenario, some huge number crunching scenario, etc. where every byte and every cycle has to count in the extreme. But the irony then is that STM seems far more suited to a language like Haskell, which is also unlikely to be suited for these performance scenarios.

My only fear is that for the masses including myself, we need *simple* mechanisms, and the fewer of those, the better. Shared nothing messages seem to scale up, out, and down. STM seems more complicated, and an incomplete solution, and only a solution for shared memory."

Indeed. Aside from Andre Pang's Erlang and Concurrency talk, I've watched Adam Welc's Google Tech Talk on Transactional Memory and am planning on listening to Simon Peyton-Jones OSCON talk on STM later today. Now, whether I'll end up listening to the other two Google Tech Talks on Transaction Memory I don't know. I have, as mentioned, read Sweeney's POPL slides.

So far, I end up thinking two things hearing these talks.
1) This is an ugly hack.
2) Overhead, overhead, overhead.

At any rate, It's nice to be involved in a high-level nerd conversation with very smart people. That's always fun.

Buffer Overflow; Core Dump

posted on 2007-08-15 13:16:08

Wow. I have been thinking about The Concurrency Problem waaaayyy too much the last 48 hours or so. I'm coming around about STM and am really hoping I get an e-mail back from Tim Sweeney answering some questions I had. Yes, that Tim Sweeney.

All the same, I'd rather Erlang or some other message passing functional+concurrent programming model get adopted than a non message-passing model such as Haskell. Erlang just seems cleaner to me. I just like it a bit better. Perhaps that will all change as I actually start trying to write code with them (Erlang, Haskell). Anyone who feels like coming along and writing something better that has the advantages of both without the disadvantages of either feel free. What I'm trying to say is, feel free to invent NBL.

Okay, here's what I've been reading:
http://www.algorithm.com.au/talks/concurrency-erlang/
http://patricklogan.blogspot.com/
http://patricklogan.blogspot.com/2007_02_04_patricklogan_archive.html
http://lambda-the-ultimate.org/node/1277
http://lambda-the-ultimate.org/node/2048#comment-25151
http://www.tbray.org/ongoing/When/200x/2007/06/07/Concurrency
http://enfranchisedmind.com/blog/archive/2007/08/13/323
http://enfranchisedmind.com/blog/archive/2007/02/08/191
http://www.dehora.net/journal/2007/08/phat_data.html
http://tech.puredanger.com/2007/08/14/concurrency-terracotta/
http://www.cincomsmalltalk.com/userblogs/ralph/blogView?showComments=true&printTitle=Erlang,_the_next_Java&entry=3364027251
http://www.defmacro.org/ramblings/concurrency.html
http://yarivsblog.com/articles/2006/08/16/why-erlang-is-a-great-language-for-concurrent-programming
And of course, the thing that started it all:
http://www.gotw.ca/publications/concurrency-ddj.htm

Twelfth Friday Refined Rant

posted on 2007-08-10 04:46:06

Okay, so my earlier post was a bit "La la la la. Look at all this crazy stuff I read today! Isn't it awesome?" and to be honest that's just not a critical enough take on everything. I mean, all that stuff I posted made me smile but that doesn't necessarily mean I should wave it in the air. With that in mind, I'd like to take a more serious look at the trends in those links and try to really address the issues that surround them. That's fairly challenging because these issues involve governance and law, technology and society, and plenty more. So I've decided since I'm not doing Linux Lessons I might as well do Steve Yegge-style rants. Just with much poorer writing, significantly less insight, and half as much alcohol. I'm by no means hammered. These will normally be on Fridays and this one was going to be on Friday but it's running a little late.

The Links
So, I posted about a lot of stuff. Web 2.0 and some of the associated blather about how open source addresses that through either Online Desktop or Open Services. Peer Production being supported by institutions/firms with examples of Wikipedia and Google Maps. The future of IT generally. Infrastructure challenges for the 21st century with regards to the internet and it's effects on business. Emerging worlds and the diminishing line between the virtual and the real. And some of the worldchanging issues, poverty, sustainability, climate change, political upheaval, etc. What can we really say about any of this? More importantly, what can we really take away from all those little blog snippets and links?

The Issues
There are a few things that I really take away. First of all there are a bunch of "World Issues". Things like Climate Change/Global Warming and the Energy Crisis, Developing Economies, Squatter Cities, and plenty else besides. I'm trying to get more informed on these fronts but right now the issues I can speak to tend to be technology issues rather than "World Issues". It's important to note that technology issues are a "World Issue" or are at least intertwined with "World Issues" when taken collectively. Technology has become too central a part of the modern world for technology's issues to not have vast repercussions. With that in mind I'd like to speak a bit more about what I can speak to, namely technology's issues. Specifically computing.

The Technology Issues
There are a few central issues or trends that jump out at me from what I posted the other day. One is that we are undoubtedly moving away from the desktop. However slowly, however gradually, it's happening. I don't know if the desktop will ever go away completely but it's diminishing in significance. Between PDAs and Smartphones, Laptops, Home Theater and Small Form Factor PCs, Amazon's Hardware as a Service efforts, and others the desktop market will continue to gradually erode. Second, we have a programming problem, specifically concurrency. This is emerging because everything is going massively parallel on both the local and network level. Between the rise of Multicore processors and the web services and datacenters popping up all over the place I'm convinced we need a better way to program for these sorts of systems. Third, Peer Production is making a big difference and this goes beyond software in many respects. There's a lot more to cover there so that's all I'll say for now. Fourth, the Law, Intellectual Property Law in particular, has a long way to go before it supports peer production models well. Our traditional notions of ownership and control are insufficient in the face of these new methods and as Steven Weber so elegantly described towards the close of The Success of Open Source we're going to have to find a way to bridge the gap there. Finally, I think it's important to note that there is a certain infrastructure that's critical today for technology to continue to operate in it's present fashion. We need energy and the electric grid, the telecommunications network, and the hardware and software stacks that make modern computing possible. For today, I'm mostly interested in covering the concurrency problem but next week I expect to write a bit about the infrastructure/stack and the gradual erosion of the desktop's significance.

The Concurrency Problem
Dijkstra was wrong, at least about concurrency, not that I blame him. I mean didn't he do concurrency research thirty years ago? For that matter, Simon Peyton-Jones is wrong too. Software Transactional Memory may in fact be the right solution but it's the solution to the wrong problem. Trying to figure out how to share state this way is a disaster. The only concurrency model I've seen that I think is at all valid is Erlang's message passing model. We need concurrency that is implicit. The most you should have to do is change a few "map"s to "pmap"s. That's it. I don't think Erlang is NBL. The syntax isn't too crazy but it's not C/Java-like enough either. The language generally is too much of a departure and not enough of an industry figure to really make it big besides. I'm not saying it doesn't have other problems I just feel like those are the ones that are going to hold it back. Could Haskell be more successful than Erlang? Well, first of all I'd have to come up with a good definition of success for programming languages. But excepting that I think the answer is yes. Hell, maybe Haskell is NBL and we'll struggle with shared state for another 30 years. I'm hoping for something a bit more drastic though. And Erlang isn't good enough. But it's the only thing I've seen that can solve the concurrency problem and that does appear to be the most prominent problem in programming from where I'm sitting. Does that mean we should have an OS written in Erlang and future applications should be written in Erlang? Do we need compositing window managers written in Erlang? Not necessarily. I suspect the desktop will be largely composed of C, C++, Python, etc for a good few years to come and probably longer, assuming the desktop sticks around another decade. That's a topic for another rant though.

The Punchline
What I'd really like to express is that I think that The Concurrency Problem is first and foremost a language problem. We need a language that makes concurrency implicit and easy. Concurrency needs to be assumed. Erlang is the only language I've seen that does that well. Whether or not something equivalent could be done with a non-message passing model such as Software Transactional Memory I don't know. Haskell may already scale from a single core system to a massively distributed or concurrent system with little or no changes to the code using a STM model. I'm not well read enough yet to know for sure. I don't think that we need to start over and re-write the OS, or desktop applications, or anything else for that matter. We need to be able to use the tools we already have. That doesn't mean that we might not benefit from parallelizing what we can but it's not our first priority. I don't believe that concurrency will be solved by getting the OS to handle threads or finding a framework or method to easily add concurrency to applications using current languages. Erlang isn't perfect either and ultimately not everything needs to be parallelized so Erlang has by no means invalidated C, Python, Ruby, Perl, Java, etc. It's just the best answer I see for one of the biggest problems programming has got.

This blog covers 2015, Books, Butler, C, Dad, Discrete Math, Displays, Education, Erlang, Essay, Gaming, Gapingvoid, HTDP, Hardware, IP Law, LISP, Lecture, Lessig, Linkpost, Linux, Lists, MPAA, Milosz, Music, Neruda, Open Source, Operating Systems, Personal, Pics, Poetry, Programming, Programming Languages, Project Euler, Quotes, Reddit, SICP, Self-Learning, Uncategorized, Webcomic, XKCD, Xmas, \"Real World\", adulthood, apple, career, careers, choices, clones, coleslaw, consumption, creation, emulation, fqa, games, goals, haltandcatchfire, heroes, injustice, ironyard, linux, lisp, lists, math, melee, metapost, milosz, music, pandemic, personal, poetry, productivity, professional, programming, ragequit, recreation, reflection, research, rip, strangeloop, vacation, work, year-in-review

View content from 2024-09, 2024-06, 2024-03, 2024-01, 2023-12, 2023-07, 2023-02, 2022-12, 2022-06, 2022-04, 2022-03, 2022-01, 2021-12, 2021-08, 2021-03, 2020-04, 2020-02, 2020-01, 2018-08, 2018-07, 2017-09, 2017-07, 2015-09, 2015-05, 2015-03, 2015-02, 2015-01, 2014-11, 2014-09, 2014-07, 2014-05, 2014-01, 2013-10, 2013-09, 2013-07, 2013-06, 2013-05, 2013-04, 2013-03, 2013-01, 2012-12, 2012-10, 2012-09, 2012-08, 2012-06, 2012-05, 2012-04, 2012-03, 2012-01, 2011-10, 2011-09, 2011-08, 2011-07, 2011-06, 2011-05, 2011-04, 2011-02, 2011-01, 2010-11, 2010-10, 2010-09, 2010-08, 2010-07, 2010-05, 2010-04, 2010-03, 2010-02, 2010-01, 2009-12, 2009-11, 2009-10, 2009-09, 2009-08, 2009-07, 2009-06, 2009-05, 2009-04, 2009-03, 2009-02, 2009-01, 2008-12, 2008-11, 2008-10, 2008-09, 2008-08, 2008-07, 2008-06, 2008-05, 2008-04, 2008-03, 2008-02, 2008-01, 2007-12, 2007-11, 2007-10, 2007-09, 2007-08, 2007-07, 2007-06, 2007-05