[oclug] Programming Wars 2.0 - September 2001

[dlinford at vcn.bc.ca]

Bart Trojanowski oclug at lists.oclug.on.ca 
> * dlinford at vcn.bc.ca <dlinford at vcn.bc.ca> [010804 23:57]:

> > I think the title of this paper answers that with a clear "no":
                ^^^^^^^^^^^^^^^^^^^

> Have you read this paper?  

Like I highlighted above. I started to after finding it, but it 
did seem a bit much at last night. That sort of reading can cause 
brain injury, I fear, if not in the right sort of state.  ;-)

It answers "no" to your apparent assumption such things 
only apply to trivial objects. I'm glad you read it... 

>   Have you ever implemented something using
> these techniques?

Why oh why does that matter? I've never "used" Special Relativity, nor 
General Relativity - should I consider those invalid 'till I do? Man!

Appended is something in an _unknown_ state (pulled out of 
an archive), to implement a counter. Tabs are set to 4.
I'm fairly certain one has to check the compiler output, 
and the behaviour for the machine architecture to know 
that this solution works. It's not exactly complex... 
This is adapted from real, working code that I designed 
and wrote (and checked compiler output, and the reference 
manual for the CPU...). Hope it says enough... 

> The implementation of a counter is quite complex.  It's almost like you

Bart, they are set up to provide formal proofs. Some folks have to 
write realtime s/w in a way that they can prove it won't accidentally 
kill someone :(or, _will_ likely deliberately kill someone ;). In the 
real world, the "real" real world, one can often reduce the complexity 
by data coming from formal analysis of other aspects of the system 
and its environment. "Too bad about your 2 year old being dead, 
Bart thought the code looked pretty good."  :-(

I'm not from that sort of realtime world, but was uncomfortable 
enough with others' assumptions on stack usage. Oh well. More of 
why my understanding issues is related to "concurrency in the large"
(or parallelism, to use a term I generally hate). CPU inheritance 
scheduling would turn most of what you understand on it's head. 
And I've heard that EV8 would have included something in h/w 
that transforms a "spin lock" into something which isn't... 

> Since you present yourself as an expert, please explain the notation,
> which I don't understand, that can be found on page 6:
> 
>         x[j].tag =3D x[N]tag :: x[j].val

I'm not an expert in "that stuff". I managed to more or less follow 
the short proof in a related paper. I'd not a hope in hell with 
the long proof, without it being _heavily_ annotated, and having 
_loads_ of time I wanted to kill! Math hurts! 

I'd done related things as early as 1980. No "OS" involved... 

> Also, can you tell me if I have identified the meaning of N correctly.

I'd have to read it. I could get lost as easily as you, if not more. 
If you want to (very) informally talk about such things, I'm here 
'till ~ the end of August - if you buy the coffee. If you expect 
me to "prove" things, leave me alone - it's not my problem. 

> What bothers me a bit more is that the spatial complexity is bounded not
> just to a polynomial of N but also of L, where L is the ranged of values

There's more to scheduling than what happens in a Unix/Linux kernel, 
and user-land processes. One cool thing about such objects, is that 
one can build these things without OS knowledge or support. I have. 

> desired to be stored in the counter.  That sucks man.  It means that,
> here in the real world, I would need upto O(L,N) bytes of memory to
> implement a counter that could count from zero to N.

I'm a bit sick of this desktop BS being called "the real world". 
"Fast enough so the user doesn't get pissed off or loose interest", 
is not "real world", in terms of time, in a way that's of concern... 

> Another thing I find amusing is the ability for three variables to be
> assigned values anatomically with no locking.

Anatomically Correct Objects. Cute, couldn't help it.  ;-)

>         S, tuple, id :=3D S * (INC, i, id, inval), (INC, i, id, inval), id + 1
> 
> =2E.. can you explain how that can be done and sustain the consistency of

[questions which sound like good paying work...]

> Anyway, say I was wrong about the inability of implementing some of the
> requirements of the implementation stated in the paper.  It's overly
> complex.  When I used spin-locks they are for very very short amounts of
> time.  [...]

Priority inversion. You don't mind dead-locks and live-locks??? 
Sometime locks are the way to go, some things they _can't_ do! 

> If there was more support from the hardware to implement Wait-Free
> objects than I would be all over it.  Just like I am all over use-counts

You just don't get it, yet. 

> Anyway, my request to prove me wrong still stands... if you think
> that a threaded prime-finding program can be written for a single CPU
> system that beats a single thread approach then please do.

As I've said, I'm not about to piss away 2 or 3 months of my life to 
prove anything to you. Get over it. It's a _toy_ problem, a contest. 
You can be uber geek, if you really, really want to be. No matter. 

darren
/* 
A wait free accumulator - no crital section locking. 
dlinford at myra.nebulus.net Wed Oct  8 18:27:34 PDT 1997
*/

NOTE: - this design is in progress -

/* initiaiziation code */

- TBD -

/* low priority side */

/* note: this may live-lock, if the high-priority side hits hard on the 
		accumulator - i.e., it is saturating the system.
*/

{
some-type tmp_count;
some-type tmp_more_count;

	tmp_count = 0;

	for (;;;) {

		more_count = 1; /* freeze the primary accumulator */

		tmp_count = count; /* grab the current count */

		count = 0; /* mark the primary acc. available to "retake" */

		if ( (tmp_more_count = more_count) =< 1) { 
			if (count == 0) {
				more_count = 0;
				break;
			}
			else break; /* his side did the cleanup */
		}
		else {	/* we've had updates */
			more_count = 0; /* re-enable the primary acc. */
			if (count == 0) {
				/* high-pri. didn't grab this extra count, 
				   and we've cleanly shut down the alternate
				   acc., so we need to account for it here. 
				*/
				tmp_count += tmp_more_count -1;
				break;
			}
			/* else - we don't know exactly what happened,  
				so we have to try again...
			*/
		}
	}
	<the result> = tmp_count;
}

/* high priority side */

{
some-type tmp_count;
	if (more_count != 0) {
		count += addition; /* primary accumulator is active */
	}
	else {
		if (count == 0) {
			/* low pri. side has released the primary acc., 
			   so we can do the cleanup here.
			*/
			count = more_count - 1 + addition;
			tmp_count = 0; 
		}
		else {
			/* use the secondary accumulator, since 
			   the system is in a state of flux.
			*/
			tmp_count += addition; 
		}
	}
}

/*-end-*/