Parallelism and Concurrency II
Hi,
After lots of debates off-list (specially with BrowserUk), I got to the
following conclusions:
- Each OS thread runs a cooperative-event-scheduler where coroutines
might be enqueued.
- map returns the buffer immediatly and enqueues a coroutine to process
the data.
- Explicit parallel markings such as the feed operator, means a new OS
thread with its own cooperative scheduler is spawned.
- Data that is shared between thread is selectively marked that way to
make sure they are thread safe.
- The actor model can be implemented in a different module.
So, a quick summary of how the following code would run is attached:
my @a := map { cheap_op($_) } == map { expensive_op($_) }, $*IN
The value sharing framework is still to be designed, but it's clear
that forcing actor model for everything was too intrusive, so we allow a
balance of shared state and massage-passing concurrency. This
balance will be implemented by modules.
comments are appreciated.
daniel
attachment: Perl6ThreadingModel.svg
Fwd: Re: Parallelism and Concurrency was Re: Ideas for aObject-Belongs-to-Thread (nntp: message 4 of 20) threading model (nntp: message 20 of 20 -lastone!-) (nntp: message 13 of 20)
--- Forwarded message --- From: nigelsande...@btconnect.com To: Dave Whipp - d...@whipp.name +nntp+browseruk+e66dbbe0cf.dave#whipp.n...@spamgourmet.com Cc: Subject: Re: Parallelism and Concurrency was Re: Ideas for aObject-Belongs-to-Thread (nntp: message 4 of 20) threading model (nntp: message 20 of 20 -lastone!-) (nntp: message 13 of 20) Date: Mon, 17 May 2010 22:31:45 +0100 On Mon, 17 May 2010 20:33:24 +0100, Dave Whipp - dave_wh...@yahoo.com +nntp+browseruk+2dcf7cf254.dave_whipp#yahoo@spamgourmet.com wrote: From that statement, you do not appear to understand the subject matter of this thread: Perl 6 concurrency model. Actually, the reason for my post was that I fear that I did understand the subject matter of the thread: seems to me that any reasonable discussion of perl 6 concurrency should not be too focused on pthreads-style threading. Okay. Now we're at cross-purposes about the heavily overloaded term threading. Whilst GPUs overload the term threading for their internal operations, they are for the most part invisible to applications programmer. And quite different to the 100,000 threads demos in the Go and Erlang documentation to which I referred. The latter being MIMD algorithms, and significantly harder to find applications for than, SIMD algorithms which are commonplace and well understood. My uses of the terms threading and threads are limited specifically to MIMD threading of two forms: Kernel threading: pthreads, Win32/64 threads etc. User-space threading: green threads; coroutines; goroutines; Actors; etc. See below for why I've been limiting myself to these two definitions. OpenCL/Cuda are not exotic $M hardware: they are available (and performant) on any PC (or Mac) that is mainstream or above. Millions of threads is not a huge number: its one thread per pixel on a 720p video frame (and I see no reason, other than performance, not to use Perl6 for image processing). If the discussion is stricly limited abstracting remote procedure calls, then I'll back away. But the exclusion of modules that map hyper-operators (and feeds, etc.) to OpenCL from the generic concept of perl6 concurrency seems rather blinkered. FWIW, I absolutely agree with you that the mapping between Perl 6 hyper-operators and (GPU-based or otherwise) SIMD instructions is a natural fit. But, in your post above you said: Pure SIMD (vectorization) is insufficient for many of these workloads: programmers really do need to think in terms of threads (most likely mapped to OpenCL or Cuda under the hood). By which I took you to mean that in-box SIMD (be it x86/x64 CPU or GPU SIMD instruction sets) was insufficient for many of the[se] workloads you were considering. And therefore took you to be suggesting that the Perl 6 should also be catering for the heterogeneous aspects of OpenCL in core. I now realise that you were distinguishing between CPU SIMD instructions and GPU SIMD instructions. But the real point here is Perl 6 doesn't need a threading model to use and benefit from using GPU SIMD. Any bog-standard single-threaded process can benefit from using CUDA or the homogeneous aspect of OpenCL where available, for SIMD algorithms. Their use can be entirely transparent to the language semantics for built-in operations like the hyper-operators. Ideally, the Perl 6 runtime would implement roles for OpenCl or CUDA for hyper-operations; fall back to CPU SIMD instructions; ad fall back again to old-fashioned loops if neither where available. This would all be entirely transparent to the Perl 6 programmer, just as utilising discrete FPUs was transparent to the C programmer back in the day. In an ideal world, Perl 6.0.0.0.0 would ship with just the looping hyper-operator implementation; and it would be down to users loading in an appropriately named Role that matched the hardware's capabilities that would then get transparently picked up and used by the hyper-operations to give them CPU-SIMD or GPU-SIMD as available. Or perhaps these would become perl6 build-time configuration options. The discussion (which originally started outside of this list), was about MIMD threading--the two categories above--in order to utilise the multiple *C*PU cores that are now ubiquitous. For this Perl 6 does need to sort out a threading model. The guts of the discussion has been kernel threading (and mutable shared state) is necessary. The perception being that by using user-threading (on a single core at a time), you avoid the need for and complexities of locking and synchronisation. And one of the (I believe spurious) arguments for the use of user-space (MIMD) threading, is that they are lightweight which allows you to runs thousands of concurrent threads. And it does. I've done it with Erlang right here on my dirt-cheap Intel Core2 Quad Q6600 processor. But, no matter how hard you try, you can never push the CPU utilisation above 25%, because those 100,000 user-threads all run
Re: Parallelism and Concurrency was Re: Ideas for a (nntp: message (nntp: message 18 of 20) 14 of 20) Object-Belongs-to-Thread threading model
Em Dom, 2010-05-16 às 19:34 +0100, nigelsande...@btconnect.com escreveu:
3) The tough-y: Closed-over variables.
These are tough because it exposes lexicals to sharing, but they are so
natural to use, it is hard to suggest banning their use in concurrent
routines.
This is the point I was trying to address, actually. Having *only*
explicitly shared variables makes it very cumbersome to write threaded
code, specially because explicitly shared variables have a lot of
restrictions on what they can be (this is from my experience in Perl 5
and SDL, which was what brought me to the message-passing idea).
However, interpreters already have to detect closed over variables in
order to 'lift' them and extend their lifetimes beyond their natural
scope.
Actually, the interpreter might choose to to implement the closed-up
variables by keeping that entire associated scope when it is still
referenced by another value, i.e.:
{ my $a;
{ my $b = 1;
{ $a = sub { $b++ } } }
this would happen by the having every lexical scope holding a reference
to its outer scope, so when a scope in the middle exits, but some
coderef was returned keeping it as its lexical outer, the entire scope
would be kept.
This means two things:
1) the interpreter doesn't need to detect the closed over variables, so
even string eval'ed access to such variables would work (which is, imho,
a good thing)
2) all the values in that lexical scope are also preserved with the
closure, even if they won't be used (which is a bad thing).
It doesn't seem it would be any harder to lift them to shared
variable status, moving them out of the thread-local lexical pads and into
the same data-space as process globals and explicitly shared data.
It is still possible to do the detection on the moment of the runtime
lookup, tho...
My currently favoured mechanism for handling shared data, is via
message-passing, but passing references to the shared data, rather than
the data itself. This seems to give the reason-ability, compose-ability
and controlled access of message passing whilst retaining the efficiency
of direct, shared-state mutability.
That was part of my idea too, I wasn't trying to address remote
processes or anything like that, I was considering doing the queues in
shared memory for its efficiency.
Only the code that declares the shared
data, plus any other thread it choses to send a handle to, has any
knowledge of, and therefore access to the shared state.
If we can overcome the limitations we have in Perl 5 shared values, I'm
entirely in agreement with the above statement (assuming closed-over
values become shared transparently)
Effectively, allocating a shared entity returns a handle to the underlying
state, and only the holder of that handle can access it. Such handles
would be indirect references and only usable from the thread that creates
them. When a handle is passed as a message to another thread, it is
transformed into a handle usable by the recipient thread during the
transfer and the old handle becomes invalid. Attempt to use an old handle
after it has been sent result in a runtime exception.
This is exactly what I meant by RemoteValue, RemoteInvocation and
InvocationQueue in my original idea.
daniel
Re: Parallelism and Concurrency was Re: Ideas for a (nntp: message (nntp: message 18 of 20) 14 of 20) Object-Belongs-to-Thread threading model
On Tue, 18 May 2010 11:39:04 +0100, Daniel Ruoso dan...@ruoso.com wrote:
This is the point I was trying to address, actually. Having *only*
explicitly shared variables makes it very cumbersome to write threaded
code, specially because explicitly shared variables have a lot of
restrictions on what they can be (this is from my experience in Perl 5
and SDL, which was what brought me to the message-passing idea).
Well, do not base anything upon the restrictions and limitations of the
Perl 5 threads/shared modules. They are broken-by-design in so many ways
that they are not a good reference point. That particular
restriction--what a :shared var can and cannot hold--is in some cases just
an arbitrary restriction for no good reason that I can see.
For example: file handles cannot be assigned to :shared vars is totally
arbitrary. This can be demonstrated in two ways:
1) If you pass the fileno of the filehandle to a thread and have it dup(2)
a copy, then it can use it concurrently with the originating thread
without problems--subject to the obvious locking requirements.
2) I've previously hacked the sources to bypass this restrict by adding
SVt_PVGV to the switch in the following function:
SV *
Perl_sharedsv_find(pTHX_ SV *sv)
{
MAGIC *mg;
if (SvTYPE(sv) = SVt_PVMG) {
switch(SvTYPE(sv)) {
case SVt_PVAV:
case SVt_PVHV:
case SVt_PVGV: // !!!
if ((mg = mg_find(sv, PERL_MAGIC_tied))
mg-mg_virtual == sharedsv_array_vtbl) {
return ((SV *)mg-mg_ptr);
}
break;
default:
/* This should work for elements as well as they
* have scalar magic as well as their element magic
*/
if ((mg = mg_find(sv, PERL_MAGIC_shared_scalar))
mg-mg_virtual == sharedsv_scalar_vtbl) {
return ((SV *)mg-mg_ptr);
}
break;
}
}
/* Just for tidyness of API also handle tie objects */
if (SvROK(sv) sv_derived_from(sv, threads::shared::tie)) {
return (S_sharedsv_from_obj(aTHX_ sv));
}
return (NULL);
}
And with that one change, sharing file/directory handles in Perl 5 became
possible and worked.
The problem is, GVs can hold far more than just those handles. And many of
the glob-modules utilise the other slots in a GV (array/hahs scalaer etc.)
for storing state and bless them as objects. At that point--when I tried
the change--the was a conflict between the blessing that Shared.XS uses to
make sharing working and any other type of blessing. The net result was
that whilst the change lifted the restriction upon simple globs, it still
didn't work with many of the most useful glob-based module--IO::Socket::*;
HTTP::Deamon; etc. I guess that now the sharing of blessed objects has
been mage possible, I shoudl try the hack again a see if it would allow
those blessed globs to work.
Anyway, the point is that the limitations and restrictions of the Perl5
implementation of the iThreads model, should not be considered as
fundamental problems with with the iThreads model itself. They aren't.
However, interpreters already have to detect closed over variables
in
order to 'lift' them and extend their lifetimes beyond their natural
scope.
Actually, the interpreter might choose to to implement the closed-up
variables by keeping that entire associated scope when it is still
referenced by another value, i.e.:
{ my $a;
{ my $b = 1;
{ $a = sub { $b++ } } }
this would happen by the having every lexical scope holding a reference
to its outer scope, so when a scope in the middle exits, but some
coderef was returned keeping it as its lexical outer, the entire scope
would be kept.
This means two things:
1) the interpreter doesn't need to detect the closed over variables, so
even string eval'ed access to such variables would work (which is, imho,
a good thing)
You'd have to explain further for me to understand why it is necessary to
keep whole scopes around:
- in order to make closures accessible from string-eval;
- and why that is desirable?
2) all the values in that lexical scope are also preserved with the
closure, even if they won't be used (which is a bad thing).
Please no! :)
This is essentially the biggest problem with the Perl 5 iThreads
implementation. It is the *need* (though I have serious doubts that it is
actually a need even for Perl 5), to CLONE entire scope stacks every time
you spawn a thread that makes them costly to use. Both because of the time
it takes to perform the clone at spawn time; and the memory used to keep
copies of all that stuff that simply isn't wanted; and in many cases isn't
even accessible. AFAIK going by what I can find about the history of
iThreads development, this was only done in Perl 5 in order to provide the
Windows fork emulation.
But as a
Re: Parallelism and Concurrency was Re: Ideas for a (nntp: message (nntp: message 18 of 20) 14 of 20) Object-Belongs-to-Thread threading model
On Tue, 18 May 2010 11:41:08 +0100, Daniel Ruoso dan...@ruoso.com wrote: Em Dom, 2010-05-16 às 19:34 +0100, nigelsande...@btconnect.com escreveu: Interoperability with Perl 5 and is reference counting should not be a high priority in the decision making process for defining the Perl 6 concurrency model. If we drop that requirement then we can simply go to the we-can-spawn-as-many-os-threads-as-we-want model.. I do not see that as a requirement. But, I am painfully aware that I am playing catchup with all the various versions, flavours and colors of Perl6 interpreter. And more importantly, the significance of each of tehm. When I recently started following #perl6 I was blown away (and totally confused) by all the various flavours that the eval bot responded to. The funny thing is that I have a serious soft spot for the timelyness of reference couting GC. And I recently came across a paper on a new RCGC that claimed to address the circular reference problem without resorting to weak references or other labour intensive mechanisms; nor a stop-the-world GC cycle. I scanned the paper and it was essentially a multi-pass coloring scheme, but achived better performaince than most by a) running locally (to scopes I think) so that it had far fewer arenas to scan. b) Using a invative coloring scheme that meant it was O(N) rather than the usual O(N * M) Most of it went over my head, (as is often the case with aademic papers), but it seems real. But I think that is a boat that has long sailed for Perl 6? daniel
Re: Re: Parallelism and Concurrency was Re: Ideas for aObject-Belongs-to-Thread (nntp: message 4 of 20) threading model (nntp: message 20 of 20 -lastone!-) (nntp: message 13 of 20)
Em Ter, 2010-05-18 às 12:58 -0700, Alex Elsayed escreveu: You are imposing a false dichotomy here. Neither 'green' threads nor kernel threads preclude each other. In fact, it can be convincingly argued that they work _best_ when combined. Please look at the GSoC proposal for hybrid threading on the Parrot list. While I agree that there isn't a dichotomy, the point here is more in the lines of: 1) Green threads are usually related to the requirement of serialized access to data so you can share all data in the thread without resorting to locks for every value. 2) If that requirement is dropped, once only data that is explicitly marked as shared can be seen by both threads, the point for green threads is moot, since the OS threads are always going to be better performant then a manually implemented scheduler. My original idea was pointing in creating a shared memory space that would be seen by every green thread in the same os thread, where some lines would be drawn to allow OS threading with different memory spaces - message passing would be used to communicate between two different memory spaces. But what we might be getting here is at the point where we don't need green threads at all... I'm still not sure about one point or another, tho.. daniel
Re: Parallelism and Concurrency was Re: Ideas for aObject-Belongs-to-Thread threading model (nntp: message 20 of 20 -lastone!-)
nigelsande...@btconnect.com wrote: There are very few algorithms that actually benefit from using even low hundreds of threads, let alone thousands. The ability of Erlang (and go an IO and many others) to spawn 100,000 threads makes an impressive demo for the uninitiated, but finding practical uses of such abilities is very hard. It may be true that there are only a small number of basic algorithms that benefit from massive parallelization. The important thing is not the number of algorithms: it's the number programs and workloads. Even if there was only one parallel algorithm, if that algorithm was needed for the majority of parallel workloads then it would be significant. In fact, though utilizing thousands of threads may be hard, once you get to millions of threads then things become interesting again. Physical simulations, image processing, search, finance, etc., are all fields that exhibit workloads amenable to large scale parallelization. Pure SIMD (vectorization) is insufficient for many of these workloads: programmers really do need to think in terms of threads (most likely mapped to OpenCL or Cuda under the hood). To use millions of threads you don't focus on what the algorithm is doing: you focus on where the data is going. If you move data unnecessarily (or fail to move it when it was necessary) then you'll burn power and lose performance.
Re: Parallelism and Concurrency was Re: Ideas for aObject-Belongs-to-Thread (nntp: message 4 of 20) threading model (nntp: message 20 of 20 -lastone!-)
[Note: removed one CCer because the email address was long and complex and looked like my mail client had hacked up a hairball full of experimental Perl 6 obfuscation. My apologies if that wasn't actually a mail failure] On Mon, May 17, 2010 at 3:13 PM, nigelsande...@btconnect.com wrote: The important thing is not the number of algorithms: it's the number programs and workloads. From that statement, you do not appear to understand the subject matter of this thread: Perl 6 concurrency model. That seems a tad more confrontational than was required. It's also arguably incorrect. Surveying existing software implementations and code bases is not precluded, simply because we're talking about a new(ish) language. For CPU-bound processes, there is no benefit in trying to utilise more than one thread per core--or hardware thread if your cores have hyper-threading. Context switches are expensive, and running hundreds (let alone thousands or millions) of threads on 2/4/8/12 core commodity hardware, means that you'll spend more time context switching than doing actual work. With the net result of less rather than more throughput. I know that you know what I'm about to say, but I'm going to say it anyway just so we're standing on the same ground. When I was in college, I had access to a loosely coupled 20-processor system. That was considered radical, cutting-edge technology for the fact that you could treat it like a standard Unix workhorse, and not as some sort of black-hole of computing power with which you could commune via a front-end (ala Cray). I then worked for a company that was producing an order 1k processor system to do the same thing. These were relatively short-spaced advances in technology. When a single die shipped, containing 2 cores, I was agape. I'd never considered that it would happen as soon as it did. Today we're putting order of 10 cores on a die. I'm really not all that old, and yet the shockingly high-end supercomputing platforms of my youth are, more or less, being put on a chip. Perl pre-6 hit its stride about 5-10 years into its lifespan (mid to late 90s). Perl 6 hasn't even shipped yet, and yet your statements appear to be selecting modern hardware as its target platform, design wise. I'm not sure that's entirely (un)wise. Then again, it does simplify the world tremendously. I just wanted to get that all out there for thought. -- Aaron Sherman Email or GTalk: a...@ajs.com http://www.ajs.com/~ajs
Re: Parallelism and Concurrency was Re: Ideas foraObject-Belongs-to-Thread (nntp: message 4 of 20) threading model (nntp:message 20 of 20 -lastone!-)
nigelsande...@btconnect.com wrote: From that statement, you do not appear to understand the subject matter of this thread: Perl 6 concurrency model. If I misunderstood then I apologize: I had thought that the subject was the underlying abstractions of parallelism and concurrency that perl6 language will define in order to enable specific threading modules to be provided by implementations. If the subject is specifically contemporary [multicore] CPU threading implementations then my comments may not be relevant. For CPU-bound processes [...]. Sure, there are exotica hardware that have thousands of cores, but it hardly seems likely that having spent $millions upon such hardware to run your massively parallel algorithms to solve problems in realistic time frames, that your going to use a dynamic (no-compiled) language to write your solutions in. Any midrange GPU will support millions of thread-launches per second. One frame of 720p video has a million pixels, and these days in not uncommon to have multiple threads per pixel. True, using a dynamic programming language for the guts of these threads is probably not a good tradeoff today: I'd probably use an Inline::OpenCL module initially. But I see no reason that a strongly statically typed subset of Perl6 could not be compiled to efficient device-code. To use millions of threads you don't focus on what the algorithm is doing: you focus on where the data is going. If you move data unnecessarily (or fail to move it when it was necessary) then you'll burn power and lose performance. Sorry, but I've got to call you on this. Parallelisation (threading) is all about improving performance. And the first three rules of performance are: algorithm; algorithm; algorithm. Choose the wrong algorithm and you are wasting cycles. Parallelise that wrong algorithm, and you're just multiplying the number of cycles you're wasting. I always thought that the first rule of performance optimization is measure (i.e. run a profiler). But ignoring that quibble, the reason that bad algorithms are bad is (usually) bad data management (either unnecessary movement, or unnecessary locking). If you want to understand why an algorithm is inefficient then you need to study the data accesses, not (just) the processing. A special case of bad data movement, that applies even to sequential code, is cache-thrashing. This is somewhat analagous to ASIC design: at around .13 um processes, wire load delays started to dominate gate delays: wires became a dominant source of delay for many paths: initially just the longer routes, but these days you can't ignore them. This doesn't mean that you can completely ignore the logic: it just means that logic optimization is taken as a given, and that the real work is in placement and routing. Similarly, while a bad algorithm is obviously bad, even a good algorithm will perform badly (i.e. will waste memory bandwidth and power) if you don't have a way to define how the data will move in the implementation of that algorithm. If you're not careful then you'll burn more power moving data from/to memory than processing it (slightly stale data: moving a 32-bit value to local dram may use 1nJ (1 nanojoule); moving that same value a millimeter onchip may burn only 10 pJ: similar to the energy of a single-precision floating point operation, but that op needs 2 source operands and must write a destination, each of which requires a data movement. You can, of course, ignore these issues if you're just managing a handful of IO-bound CPU threads. Feel free to tell me that perl6 will never be used in scenarios where such considerations are important. I'll probably disagree. But I could probably be persuaded that the the current type-system has sufficient mechanisms (via traits) to define data placement without any new features. And therefore the issue can be ignored until someone actually attempts to implement OpenCL bindings. Dave.
Re: Parallelism and Concurrency was Re: Ideas for a Object-Belongs-to-Thread threading model (nntp: message 20 of 20 -last one!-)
On Fri, 14 May 2010 17:35:20 +0100, B. Estrade - estr...@gmail.com +nntp+browseruk+c4c81fb0fa.estrabd#gmail@spamgourmet.com wrote: The future is indeed multicore - or, rather, *many-core. What this means is that however the hardware jockeys have to strap them together on a single node, we'll be looking at the ability to invoke hundreds (or thousands) of threads on a single SMP machine. There are very few algorithms that actually benefit from using even low hundreds of threads, let alone thousands. The ability of Erlang (and go an IO and many others) to spawn 100,000 threads makes an impressive demo for the uninitiated, but finding practical uses of such abilities is very hard. One example cited is that of gaming software that runs each sprite ina separate thread. The claim is that this simplifies code because each sprite only has to respond to situations directly applicable to it, rather than some common sprite handler having to select which sprite to operate upon. But all it does is move the goal posts. You either have to select which sprite to send a message to; or send a message to the sprite handler and have it select the sprite to operate upon. A third technique is to send the message to all the sprites and have then decide if it is applicable to them. But it still requires a loop, and you then have the communications overhead *100,000 + the context witch costs * 100,000. The numbers do not add up. Then, inevitably, *someone will want to strap these together into a cluster, thus making message passing an attractive way to glue related threads together over a network. Getting back to the availability of many threads on a single SMP box, issues of data locality and affinity and thread binding will become of critical importance. Perhaps surprisingly, these are not the issues they once were. Whilst cache misses are horribly expensive, the multi-layered caching in modern CPUs combines with deep pipelines, branch prediction, register renaming and other features in ways that are beyond the ability of the human mind to reason about. For a whirlwind introduction to the complexities, see the short video here: http://www.infoq.com/presentations/click-crash-course-modern-hardware The only way to test the affects is to profile, and most of the research into the effects of cache locality tend to be done in isolation of real-world application mixes. very few machines, even servers of various types, run a single application these days. This is even truer as server virtualisation becomes ubiquitous. Mix in a soupçon of virtual server load-balancing and trying to code for cache locality becomes almost impossible. These issues are closely related to the operating system's capabilities and paging policies, but eventually (hopefully) current, provably beneficial strategies will be available on most platforms. Brett
Parallelism and Concurrency was Re: Ideas for a Object-Belongs-to-Thread threading model
After reading this thread and S17, I have lots of questions and some remarks. Parallelism and Concurrency could be considered to be two different things. The hyperoperators and junctions imply, but do not require, parallelism. It is left for the implementors to resolve whether a single or multiple processor(s) is/are used. Hence, parallelism could be considered to be something under the hood of perl6 and not directly specified. Given that: - concurrency is a topic of ongoing research - several models of concurrency have been tried, including two in perl5 - there are a variety of contexts (internet, clouds, multiple cores, etc) - different operating systems provide different resources then: How much needs to be specified and implemented in perl6 so that different concurrency models can be implemented in modules to take into account the above diversity? The less, or rather the more abstract, the specification in perl6, the less likely perl6 will 'age'. On 05/12/2010 09:12 PM, Dave Whipp wrote: Daniel Ruoso wrote: Hi, The threading model topic still needs lots of thinking, so I decided to try out some ideas. Every concurrency model has its advantages and drawbacks, I've been wondering about this ideas for a while now and I think I finally have a sketch. My primary concerns were: 1 - It can't require locking: Locking is just not scalable; 2 - It should perform better with lots of cores even if it suffers when you have only a few; 3 - It shouldn't require complicated memory management techniques that will make it difficult to bind native libraries (yes, STM is damn hard); 4 - It should suport implicit threading and implicit event-based programming (i.e. the feed operator); 5 - It must be easier to use then Perl 5 shared variables; 6 - It can't use a Global Interpreter Lock (that already said in 1, but, as this is a widely accepted idea in some other environments, I thought it would be better to make it explicit). The idea I started was that every object has an owner thread, and only that thread should talk to it, and I ended up with the following, comments are appreciated: comments? ideas? Before discussing the implementation, I think it's worth while stating what it is that you are attempting to abstract. For example, is the abstraction intended for a mapping down to a GPU (e.g. OpenCL) with a hierarchical address space, or is it intended for a multicore CPU with linear address space, or is it intended to abstract a LAN, with communication via sockets (reliable TCP? unreliable UDP?), or is it intended to abstract the internet/cloud? Are you thinking in terms of streaming computation where throughput is dominant, or interacting agents where latency is the critical metric? I'm not sure that it makes sense to talk of a single abstraction that supports all of those environments. However, there may be bunch of abstractions that can be combined in different ways. object belongs to thread can have two interpretations: one is that the object-thread binding lasts for the life of the object; the other is that a client that wishes to use an object must request ownership, and wait to be granted (in some scenarios, the granting of ownership would require the thread to migrate to the physical processor that owns the state). In many cases, we might find that specific object-state must live in specific places, but not all of the state that is encapsulated by an object lives in the same place. Often, an object will encapsulate state that is, itself, accessed via objects. If a model requires delegated access to owned state to be passed through an intermediate object then this may imply significant overhead. A better way to think about such scenarios may be that a client would request access to a subset of methods -- and thus we have role belongs to thread, not object belongs to thread. One could imagine that a FIFO object might have a put role and a get role that producer/consumer clients would (temporarily) own while using (note that granting of ownership may imply arbitration, and later forced-revocation if the resource-ownership is not released/extended before some timeout expires). It may be wrong to conflate role as a unit of reuse with role as an owned window onto a subset of an object's methods. Perl6 has a set of language primitives to support various aspects of concurrency. It is indeed interesting to consider how these map ot vastly difference computation platforms: OpenCl Vs OpenMP Vs Cloud. It deeps a little premature to be defining roles (e.g. RemoteInvocation) without defining the mapping of the core operators to these various models of computation. Dave.
Re: Parallelism and Concurrency was Re: Ideas for a Object-Belongs-to-Thread threading model
On Fri, May 14, 2010 at 03:48:10PM +0400, Richard Hainsworth wrote: : After reading this thread and S17, I have lots of questions and some : remarks. : : Parallelism and Concurrency could be considered to be two different things. : : The hyperoperators and junctions imply, but do not require, : parallelism. It is left for the implementors to resolve whether a : single or multiple processor(s) is/are used. Hence, parallelism : could be considered to be something under the hood of perl6 and not : directly specified. Certainly we've put in a number of abstract constructs that, if used by the programmer, make promises of parallelizability, even if the the implementation makes no promises about actual parallelization. : Given that: : - concurrency is a topic of ongoing research : - several models of concurrency have been tried, including two in perl5 : - there are a variety of contexts (internet, clouds, multiple cores, etc) : - different operating systems provide different resources : : then: : How much needs to be specified and implemented in perl6 so that : different concurrency models can be implemented in modules to take : into account the above diversity? : : The less, or rather the more abstract, the specification in perl6, : the less likely perl6 will 'age'. Yes, but... We need to understand the possibilities sufficiently well to provide a default implementation that most modules can code to, or we'll simply end up with a mess of incompatible modules. This goes doubly for the standard library; if it is written in a way that violates the constraints of a thread model, it will not be useable under that model. (See the Perl 5 ecosystem for what happens if you bolt on threading after the fact.) So what we're primarily trying to understand and predict is how the various threading models will constrain us in our normal coding patterns, and how we can make those constraints as invisible as possible without either violating them by accident or inducing unnecessary overhead. Requiring the programmer to make a few minor accomodations to achieve this may buy us a lot of non-grief in the future. But as you say, this is not a simple problem to solve; our response should not be to punt this to future generations, but to solve it as best as we can, and hope we can make some of the hard decisions right enough to allow future evolution. I am very glad to see several passionate but mostly-rational people thrashing this out here; the future is many-core, and none of us understand the implications of that well enough yet to write off the topic as a bikeshed, or to wish for the good old days of single core. Sure, it should be possible to write a Perl program in a single-threaded mindset, but while certain popular languages cling to the past and try to make single-threadedness a feature, Perl is more about embracing the future and about freeing the programmer from arbitrary restrictions. And as Perl 5 OO demonstrated, sometimes not picking a good default can be just about as damaging as picking the wrong one. Note also that the fundamental difficulty with doing threading in Perl 5 is not the exact model chosen, but rather that the fundamental underpinnings of locality were (for various historical reasons) poorly designed/evolved in the first place, so we ended up with far too much information having to be managed outside of its proper scope, for many different definitions of scope. This has been one of the secret sauces of the Perl 6 redesign, to hang every piece of information on the peg where it belongs, and not somewhere else. And that is why threading of *any* kind will work much better in Perl 6. Larry
Re: Parallelism and Concurrency was Re: Ideas for a (nntp: message 14 of 20) Object-Belongs-to-Thread threading model
Em Sex, 2010-05-14 às 18:13 +0100, nigelsande...@btconnect.com escreveu: The point I(we)'ve been trying to make is that once you have a reentrant interpreter, and the ability to spawn one in an OS thread, all the other bits can be built on top. But unless you have that ability, whilst the others can be constructed, the cannot make use of SMP. Eg. They cannot scale. Okay, this is an important point... Having a reentrant interpreter is a given already, The form I tried to implement that in SMOP was by using CPS. The idea of using green threads is just to enforce serialized access to some data in order to avoid locking (locking with the amount of polymorphism required by Perl 6 is too expensive), and then the regular threads wouldn't share data between them. Of course we could try to have the data structures thread-safe, I didn't try to go that path since I was trying to get Perl 5 interoperability and therefore used refcount garbage collector. The other possibility would be to use processor affinity to force different threads to spawn in the same processor and that way ensure serialized access to the non-thread-safe data. daniel
Re: Parallelism and Concurrency was Re: Ideas for a Object-Belongs-to-Thread threading model
On Fri, May 14, 2010 at 03:48:10PM +0400, Richard Hainsworth wrote: After reading this thread and S17, I have lots of questions and some remarks. Parallelism and Concurrency could be considered to be two different things. The hyperoperators and junctions imply, but do not require, parallelism. It is left for the implementors to resolve whether a single or multiple processor(s) is/are used. Hence, parallelism could be considered to be something under the hood of perl6 and not directly specified. Given that: - concurrency is a topic of ongoing research - several models of concurrency have been tried, including two in perl5 - there are a variety of contexts (internet, clouds, multiple cores, etc) - different operating systems provide different resources then: How much needs to be specified and implemented in perl6 so that different concurrency models can be implemented in modules to take into account the above diversity? The less, or rather the more abstract, the specification in perl6, the less likely perl6 will 'age'. I might be over simplifying this, but you're going to be building on essentially 2 different underlying approaches - one is message passing. The second is threading - I mean *real* threading. If these basic facilities are provided in the base, or even via a couple of robust and tightly integrated modules, then I believe any other scheme one wishes to implement (even a hybrid scheme), could be done so - thus solidifying Perl 6's ability to implement the parallel scheme de jour. Brett On 05/12/2010 09:12 PM, Dave Whipp wrote: Daniel Ruoso wrote: Hi, The threading model topic still needs lots of thinking, so I decided to try out some ideas. Every concurrency model has its advantages and drawbacks, I've been wondering about this ideas for a while now and I think I finally have a sketch. My primary concerns were: 1 - It can't require locking: Locking is just not scalable; 2 - It should perform better with lots of cores even if it suffers when you have only a few; 3 - It shouldn't require complicated memory management techniques that will make it difficult to bind native libraries (yes, STM is damn hard); 4 - It should suport implicit threading and implicit event-based programming (i.e. the feed operator); 5 - It must be easier to use then Perl 5 shared variables; 6 - It can't use a Global Interpreter Lock (that already said in 1, but, as this is a widely accepted idea in some other environments, I thought it would be better to make it explicit). The idea I started was that every object has an owner thread, and only that thread should talk to it, and I ended up with the following, comments are appreciated: comments? ideas? Before discussing the implementation, I think it's worth while stating what it is that you are attempting to abstract. For example, is the abstraction intended for a mapping down to a GPU (e.g. OpenCL) with a hierarchical address space, or is it intended for a multicore CPU with linear address space, or is it intended to abstract a LAN, with communication via sockets (reliable TCP? unreliable UDP?), or is it intended to abstract the internet/cloud? Are you thinking in terms of streaming computation where throughput is dominant, or interacting agents where latency is the critical metric? I'm not sure that it makes sense to talk of a single abstraction that supports all of those environments. However, there may be bunch of abstractions that can be combined in different ways. object belongs to thread can have two interpretations: one is that the object-thread binding lasts for the life of the object; the other is that a client that wishes to use an object must request ownership, and wait to be granted (in some scenarios, the granting of ownership would require the thread to migrate to the physical processor that owns the state). In many cases, we might find that specific object-state must live in specific places, but not all of the state that is encapsulated by an object lives in the same place. Often, an object will encapsulate state that is, itself, accessed via objects. If a model requires delegated access to owned state to be passed through an intermediate object then this may imply significant overhead. A better way to think about such scenarios may be that a client would request access to a subset of methods -- and thus we have role belongs to thread, not object belongs to thread. One could imagine that a FIFO object might have a put role and a get role that producer/consumer clients would (temporarily) own while using (note that granting of ownership may imply arbitration, and later forced-revocation if the resource-ownership is not released/extended before some timeout expires). It may be wrong to conflate role as a unit of reuse with role as an owned window onto a subset of an object's
Re: Parallelism and Concurrency was Re: Ideas for a Object-Belongs-to-Thread threading model
On Fri, May 14, 2010 at 09:50:21AM -0700, Larry Wall wrote: On Fri, May 14, 2010 at 03:48:10PM +0400, Richard Hainsworth wrote: ...snip But as you say, this is not a simple problem to solve; our response should not be to punt this to future generations, but to solve it as best as we can, and hope we can make some of the hard decisions right enough to allow future evolution. I am very glad to see several passionate but mostly-rational people thrashing this out here; the future is many-core, and none of us understand the implications of that well enough yet to write off the topic as a bikeshed, or to wish for the good old days of single core. Sure, it should be possible to write a Perl program in a single-threaded mindset, but while certain popular languages cling to the past and try to make single-threadedness a feature, Perl is more about embracing the future and about freeing the programmer from arbitrary restrictions. And as Perl 5 OO demonstrated, sometimes not picking a good default can be just about as damaging as picking the wrong one. The future is indeed multicore - or, rather, *many-core. What this means is that however the hardware jockeys have to strap them together on a single node, we'll be looking at the ability to invoke hundreds (or thousands) of threads on a single SMP machine. Then, inevitably, *someone will want to strap these together into a cluster, thus making message passing an attractive way to glue related threads together over a network. Getting back to the availability of many threads on a single SMP box, issues of data locality and affinity and thread binding will become of critical importance. These issues are closely related to the operating system's capabilities and paging policies, but eventually (hopefully) current, provably beneficial strategies will be available on most platforms. Brett Note also that the fundamental difficulty with doing threading in Perl 5 is not the exact model chosen, but rather that the fundamental underpinnings of locality were (for various historical reasons) poorly designed/evolved in the first place, so we ended up with far too much information having to be managed outside of its proper scope, for many different definitions of scope. This has been one of the secret sauces of the Perl 6 redesign, to hang every piece of information on the peg where it belongs, and not somewhere else. And that is why threading of *any* kind will work much better in Perl 6. Larry -- B. Estrade estr...@gmail.com
Re: S17-concurrency question
Em Seg, 2009-02-16 às 17:28 +1100, Timothy S. Nelson escreveu:
Say I wanted to write a POP3 server. I want to receive a username and
password from the client. I want things to be interruptable during this, but
it's also impossible to sensibly roll things back like they were before the
connection was opened. Is this possible with the concurrency model you
specified?
The things you're describing are from the time when we were assuming STM
(Software Transactional Memory) would be used by every implementation of
Perl 6. Things have changed a bit in the last months, as STM seems a bit
more challenging then it looks at first sight for a language as complex
as Perl 6, specially if you think about lazyness.
OTOH, the problem POE solves is the lack of a good green threads
implementation in perl 5, which I think is not a problem for Perl 6 (I
can say that for sure about SMOP, but I'm pretty sure that is also valid
for parrot).
In that specific area of writing network servers, I've been with a fixed
idea about providing autothreading code, so you can write code that
looks like 'imperative block-wait programming', but is actually 'async
non-blocking programming'. I'll paste my last sketch about it here:
my $io = Net::TCP.listen(:hostlocalhost, :port(1234));
$io does IO::Async[EV];
$io.accepts: - $conn {
my %headers;
my $data;
my $waiting_headers = 1;
for =$conn - $line {
if ($line $waiting_headers) {
my ($name, $val) = split(/\s*:\s*/, $line);
$headers{$name} = $val;
} elsif ($line) {
$data ~= $line;
} else {
$waiting_headers = 0;
}
}
$conn.write(200 OK\n\nSucessfull request\n);
};
EV.loop;
daniel
Re: S17-concurrency question
On Mon, 16 Feb 2009, Daniel Ruoso wrote: Em Seg, 2009-02-16 às 17:28 +1100, Timothy S. Nelson escreveu: Say I wanted to write a POP3 server. I want to receive a username and password from the client. I want things to be interruptable during this, but it's also impossible to sensibly roll things back like they were before the connection was opened. Is this possible with the concurrency model you specified? The things you're describing are from the time when we were assuming STM (Software Transactional Memory) would be used by every implementation of Perl 6. Things have changed a bit in the last months, as STM seems a bit more challenging then it looks at first sight for a language as complex as Perl 6, specially if you think about lazyness. OTOH, the problem POE solves is the lack of a good green threads implementation in perl 5, which I think is not a problem for Perl 6 (I can say that for sure about SMOP, but I'm pretty sure that is also valid for parrot). I agree that's what it solves, although it has many other capabilities. What I guess I'm interested in seeing is a consistent threads interface which as much as possible (and it may not always be possible) can be used across platforms, whether the backend is OS threads or green threads. In that specific area of writing network servers, I've been with a fixed idea about providing autothreading code, so you can write code that I think you a word out (possibly I've been [playing] with...?) looks like 'imperative block-wait programming', but is actually 'async non-blocking programming'. I'll paste my last sketch about it here: POE looks like it does something very similar. It works with any kind of event loop, though, not just IO. I just discovered POE yesterday, so it still seems very cool to me; we'll see in another month :). :) - | Name: Tim Nelson | Because the Creator is,| | E-mail: wayl...@wayland.id.au| I am | - BEGIN GEEK CODE BLOCK Version 3.12 GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V- PE(+) Y+++ PGP-+++ R(+) !tv b++ DI D G+ e++ h! y- -END GEEK CODE BLOCK-
S17-concurrency question
Hi. I have a question for the S17-concurrency people. Say I wanted to write a POP3 server. I want to receive a username and password from the client. I want things to be interruptable during this, but it's also impossible to sensibly roll things back like they were before the connection was opened. Is this possible with the concurrency model you specified? I've been looking at POE ( http://search.cpan.org/~rcaputo/POE-1.003/ ) and have observed that it contains its own simulated concurrency (Sessions, he calls them), and is, it seems to me, well-designed for doing external data transfer as in POP3. He uses an event-driven model. Anyway, I'll be interested to hear about this. :) - | Name: Tim Nelson | Because the Creator is,| | E-mail: wayl...@wayland.id.au| I am | - BEGIN GEEK CODE BLOCK Version 3.12 GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V- PE(+) Y+++ PGP-+++ R(+) !tv b++ DI D G+ e++ h! y- -END GEEK CODE BLOCK-
Concurrency
This last SOTO re-reminded me of what an inveterate fan I am of Perl 6. Wow. My question today is about concurrency. I can imagine how things like IPC Mailboxes (e.g. RFC 86) happen in modules. I can also imagine why Threads (e.g. RFC 1) should be in modules- given the obvious dependence on underlying OS. I do see both Cfork and Cwait in S29, but not in STD.pm, which brings me to the questions: * Where will Cfork, Cwait, and possible friends (e.g. Perl 5's Copen-with-|) live? * Is there any expectation of message-passing concurrency functions living inside STD.pm? * How about shared/software-transactional memory? Hopefully I'm not inadvertently starting any kind of flame-fest about anyone's favorite concurrency model here :-D Best, David. Never miss a thing. Make Yahoo your home page. http://www.yahoo.com/r/hs
Re: Concurrency
I'll try to reply as good as possible, but I'm sure others will do better. David Brunton wrote: This last SOTO re-reminded me of what an inveterate fan I am of Perl 6. Wow. My question today is about concurrency. I can imagine how things like IPC Mailboxes (e.g. RFC 86) happen in modules. I can also imagine why Threads (e.g. RFC 1) should be in modules- given the obvious dependence on underlying OS. I do see both Cfork and Cwait in S29, but not in STD.pm, which brings me to the questions: There's no need for any keyword to be in STD.pm. STD.pm just defines the grammar. Syntactically fork will be like just another sub, so it can safely be handled in the compiler's runtime. * Where will Cfork, Cwait, and possible friends (e.g. Perl 5's Copen-with-|) live? What do you mean by where? The namespace? Or the implementation? * Is there any expectation of message-passing concurrency functions living inside STD.pm? Again it won't be in STD.pm, because it doesn't care about it. But I think there will be both event based and thread based concurrency in Perl 6. Larry Wall usually points to this paper: http://www.seas.upenn.edu/~lipeng/homepage/unify.html Something like that, with a perlish interface, will be part of Perl 6's concurrency model. * How about shared/software-transactional memory? Yes. Maybe http://svn.pugscode.org/pugs/docs/Perl6/Spec/Concurrency.pod (still a draft) contains a bit more helpful information. Hopefully I'm not inadvertently starting any kind of flame-fest about anyone's favorite concurrency model here :-D Why flame, when we can have all of them at once? ;-) Moritz -- Moritz Lenz http://moritz.faui2k3.org/ | http://perl-6.de/ signature.asc Description: OpenPGP digital signature
Re: Concurrency: hypothetical variables and atomic blocks
Jonathan Scott Duff [EMAIL PROTECTED] wrote: On Thu, Jun 01, 2006 at 02:22:12PM -0700, Jonathan Lang wrote: Forgive this ignorant soul; but what is STM? Software Transaction Memory Well, Software Transactional Memory if I'm being picky. :-) Some info and an interesting paper here:- http://www.cambridge.intel-research.net/~rennals/faststm.html Jonathan
Re: Concurrency: hypothetical variables and atomic blocks
At 1:50 PM -0700 6/1/06, Larry Wall wrote: As for side-effecty ops, many of them can just be a promise to perform the op later when the transaction is committed, I suspect. Yes, but it would be important to specify that by the time control is returned to whatever invoked the op, that any side effects will have been successful as well, or a failure/exception is still thrown. What happens in Perl itself and what happens as external side effects are tied together from the invoker's point of view as one unit that should entirely succeed or entirely fail. Even if the side-effects are put off as late as possible in the transaction, we still need to know whether they succeeded or not. On a related note, if there is some external system used in a transaction that can't guarantee a successful rollback on failure, then any error returned by the Perl op to its invoker should differentiate between whether a failure included a successful rollback in the external system, or whether said system is now possibly or actually in an inconsistent state, so the invoker knows whether or not it should be safe to proceed. Similarly, if the external system can't guarantee successful completion before it returns control, the invoker should know that vs when completion is guaranteed. In other words, an invoker of an op should know whether the op is ACID compliant in all parts of its operation or not. -- Darren Duncan
Re: Concurrency: hypothetical variables and atomic blocks
Darren Duncan schreef: Each time a context (a code block, either a routine or a syntactic construct like 'try' is) is entered that is marked 'is atomic', a new transaction begins, which as a whole can later be committed or rolled back; it implicitly commits if that context is exited normally, and it rollsback implicitly if the context exits with a 'fail' and/or due to a thrown exception. (And yes, I see it as being easier to use if rollback and fail are generally joined at the hip.) There are also 'lazy atomic' actions that may not achieve (yet) what they are supposed to do (maybe the storage of some memory structure to a disk file). So they sort of 'try' and then sort of 'fail', but they shouldn't block continuation yet, because they will get another go at it later on. One atomic context can contain another atomic context, so they are layered; if an outer layer rolls back, it results in any 'successful' inner layers also rolling back, so that everything which happened within the outer context has rolled back. If the 'results' would be (for example) text data written to a logfile, the 'roll back' could be (1) removal of the written data, or (2) appending a line about the failure. But writing that last line can of course also fail. -- Groet, Ruud
Re: Concurrency: hypothetical variables and atomic blocks
On Thu, Jun 01, 2006 at 11:52:59AM +1200, Sam Vilain wrote: : The lock on entry approach will only be for non-threaded interpreters : that don't know how to do real STM. The way I see it, the fundamental difference is that with ordinary locking, you're locking in real time, whereas with STM you potentially have the ability to virtualize time to see if there's a way to order the locks in virtual time such that they still make sense. Then you just pretend that things happened in that order. As for side-effecty ops, many of them can just be a promise to perform the op later when the transaction is committed, I suspect. Larry
Re: Concurrency: hypothetical variables and atomic blocks
Larry Wall wrote: The way I see it, the fundamental difference is that with ordinary locking, you're locking in real time, whereas with STM you potentially have the ability to virtualize time to see if there's a way to order the locks in virtual time such that they still make sense. Then you just pretend that things happened in that order. Forgive this ignorant soul; but what is STM? -- Jonathan Dataweaver Lang
Re: Concurrency: hypothetical variables and atomic blocks
On Thu, Jun 01, 2006 at 02:22:12PM -0700, Jonathan Lang wrote: Larry Wall wrote: The way I see it, the fundamental difference is that with ordinary locking, you're locking in real time, whereas with STM you potentially have the ability to virtualize time to see if there's a way to order the locks in virtual time such that they still make sense. Then you just pretend that things happened in that order. Forgive this ignorant soul; but what is STM? Software Transaction Memory -Scott -- Jonathan Scott Duff [EMAIL PROTECTED]
Concurrency: hypothetical variables and atomic blocks
How does an atomic block differ from one in which all variables are implicitly hypotheticalized? I'm thinking that a retry exit statement may be redundant; instead, why not just go with the existing mechanisms for successful vs. failed block termination, with the minor modification that when an atomic block fails, the state rolls back? Also, what can retry_with do that testing the atomic block for failure can't? -- Jonathan Dataweaver Lang
Re: Concurrency: hypothetical variables and atomic blocks
How does an atomic block differ from one in which all variables are implicitly hypotheticalized? I assume that the atomicness being controlled by some kind of lock on entry, it also applies to I/O and other side-effecty things that you can't undo. -- Hats are no worse for being made by ancient hatters, and good butter can be bought in a shop that has no jazz-band. -- J.B. Morton (Beachcomber) P.S. --- Tell Saunders that he must not leave cat's meat on my desk. http://surreal.istic.org/ old-fashioned quality within the McQuary limit pgpztA7bT8kxG.pgp Description: PGP signature
Re: Concurrency: hypothetical variables and atomic blocks
Jonathan Lang wrote: How does an atomic block differ from one in which all variables are implicitly hypotheticalized? I'm thinking that a retry exit statement may be redundant; instead, why not just go with the existing mechanisms for successful vs. failed block termination, with the minor modification that when an atomic block fails, the state rolls back? State rolling back automatically is the key feature of STM. However, it can only cover pure perl state; any time that you enter a function that performs I/O of any kind, then you are forcing bad things to happen. With Haskell this is sorted out by making the default pure, and everything else must be in a Monad. However we're not into bondage here so is pure is not default. Instead we just die and rollback just before I/O is attempted. In principle, the compiler could automatically attach pure traits to all functions and methods that it can prove will never perform I/O and warn about this at compile time. It might be possible for clever classes to circumvent this and carefully call special unsafeIO() methods, and be passed messages about the STM and hope that they do the right thing. I don't know that anyone's explored this area in depth in Perl 6 space. Also, what can retry_with do that testing the atomic block for failure can't? I think the answer lies in the checkpointing references in that document. I don't know whether that's akin to a SQL savepoint (ie, a point mid-transaction that can be rolled back to, without committing the entire transaction) or more like a continuation that when resumed can see the atomic changes, and when exiting finally applies them (or rolls back). Perhaps someone else will have more of a clue. Sam.
Re: Concurrency: hypothetical variables and atomic blocks
Daniel Hulme wrote: How does an atomic block differ from one in which all variables are implicitly hypotheticalized? I assume that the atomicness being controlled by some kind of lock on entry, it also applies to I/O and other side-effecty things that you can't undo. The lock on entry approach will only be for non-threaded interpreters that don't know how to do real STM. Sam.
Re: Concurrency: hypothetical variables and atomic blocks
At 11:51 AM +1200 6/1/06, Sam Vilain wrote:
I think the answer lies in the checkpointing references in that
document. I don't know whether that's akin to a SQL savepoint (ie, a
point mid-transaction that can be rolled back to, without committing the
entire transaction) or more like a continuation that when resumed can
see the atomic changes, and when exiting finally applies them (or rolls
back). Perhaps someone else will have more of a clue.
Sam.
Rather than thinking about save points, it would be better to think
of the problem in terms of child transactions. (Note that what I'm
saying here is simplified to assume there aren't any irreversable
actions, but it can easily be extended to handle those situations
too.)
Each time a context (a code block, either a routine or a syntactic
construct like 'try' is) is entered that is marked 'is atomic', a new
transaction begins, which as a whole can later be committed or rolled
back; it implicitly commits if that context is exited normally, and
it rollsback implicitly if the context exits with a 'fail' and/or due
to a thrown exception. (And yes, I see it as being easier to use if
rollback and fail are generally joined at the hip.)
One atomic context can contain another atomic context, so they are
layered; if an outer layer rolls back, it results in any 'successful'
inner layers also rolling back, so that everything which happened
within the outer context has rolled back.
If we simply have child atomic contexts to implement sub-transactions
of a parent atomic context / transaction, rather than relying on
savepoints or whatever, then it is much easier to make reusable or
movable or recursive code, since the code doesn't have to specify its
own atomicness differently depending on whether its caller is being
atomic or not.
Eg, we could have a situation like this:
sub foo is atomic { ... }
sub bar is atomic { ... }
sub baz is atomic { ... }
sub quux is atomic {
...
foo();
...
try {
bar();
}
catch {
baz();
}
...
}
quux();
All 4 of the above subroutines are individually atomic and will throw
an exception / return 'fail' and rollback on failure. If quux()
fails or foo() or baz() fail, nothing that either of those 3
subroutines did will persist. If bar() fails, but baz() succeeds,
then only what bar() did has rolled back, and the rest persists when
quux() returns.
Those are my thoughts concerning transactions. I haven't
specifically addressed any matters related to exclusivity of
resources in the cases of multiple processes or threads, but they can
easily be added onto what I stated, which is also useful when there
is just a single process with a single thread.
-- Darren Duncan
