Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Implementing an observer

Reply
Thread Tools

Implementing an observer

 
 
Gene
Guest
Posts: n/a
 
      11-23-2010
On Nov 19, 4:14*am, jacob navia <(E-Mail Removed)> wrote:
> Le 19/11/10 01:48, Mark Wooding a écrit :
>
> > jacob navia<(E-Mail Removed)> *writes:

>
> >> (1) Add a slot to the header object.

>
> > This might not be too bad if there are other optional features which
> > require additional state and could share the same pointer. *I can't
> > think of any obvious examples offhand, though.

>
> In most cases, you just use a list. In some rare cases, you want to have
> a list that notifies you about changes. So, in most cases that slot
> would be wasted...
>
> >> (2) Add some global list to the software that would maintain a list
> >> * * *(or hash table) of containers,

>
> > Hashing pointers can't be done portably, but it would work much faster
> > than a (properly portable) list on the (common) platforms where it can
> > be done.

>
> >> Has anyone here any better solution?

>
> > Introduce subclasses supporting observation? *Then you pay for it only
> > if you (expect to) use it.

>
> That is complicated in C.
>
> > A nonportable trick which might work: allocate container headers in
> > chunks with some known alignment, so that you can find the chunk base
> > easily given the header. *Add a flag to each container header to say
> > whether it uses an extension record. *Use a single word at the start of
> > the chunk to point to an extension record table for all the headers in
> > the chunk: the first time you need an extension record for one header,
> > allocate the extension record table for the chunk and an extension
> > record for the particular header. *In the absence of contention, you
> > only pay one CAS for each chunk which needs an extension record. *Memory
> > overheads are one word per chunk, plus one word per header if any
> > extension records are used, plus the needed extension records
> > themselves.

>
> Wow that is a clever schema. I think the essential point is to allocate
> as needed, to avoid wasted storage. Thanks a lot for this idea.
>
>
>
>
>
> > Example (completely untested!):

>
> > * * * * *#define NCHUNK 16

>
> > * * * * *struct ext {
> > * * * * * */* ... */
> > * * * * *};

>
> > * * * * *struct hdr {
> > * * * * * *unsigned f;
> > * * * * *#define F_EXT 1u
> > * * * * * */* ... */
> > * * * * *};

>
> > * * * * *struct chunk {
> > * * * * * *struct ext **xv;
> > * * * * * *struct hdr hv[NCHUNK];
> > * * * * *};

>
> > * * * * *struct ext *ensure_ext(struct hdr *h)
> > * * * * *{
> > * * * * * *struct chunk *c = CHUNK_BASE(h);
> > * * * * * *struct chunk **xv = c->xv;
> > * * * * * *int i = h - c->hv;

>
> > * * * * * */* Quick check for extension record. */
> > * * * * * *if (!(h->f& *F_EXT)) {

>
> > * * * * * * */* Ensure extension vector for the chunk exists: attention
> > * * * * * to concurrency required.
> > * * * * * * * */
> > * * * * * * *if (!xv) {
> > * * * * * * * *if ((xv = malloc(NCHUNK * sizeof(*xv))) == 0)
> > * * * * * * * * *return (0);
> > * * * * * * * *if (COMPARE_AND_SWAP(c->xv, xv, 0)) {
> > * * * * * * * * *free(xv);
> > * * * * * * * * *xv = c->xv;
> > * * * * * * * *}
> > * * * * * * *}

>
> > * * * * * * */* Ensure extension record for the header. *Assume single
> > * * * * * threaded access to the header. *This can't be allocated yet.
> > * * * * * * * */
> > * * * * * * *if ((xv[i] = malloc(sizeof(struct ext))) == 0)
> > * * * * * * * *return (0);
> > * * * * * * *h->f |= F_EXT;
> > * * * * * *}

>
> > * * * * * */* Done. */
> > * * * * * *return (xv[i]);
> > * * * * *}

>
> >> By the way, does anyone know how is this implemented in the C++ STL (if at
> >> all)?

>
> > It isn't. *You'd have to subclass manually.

>
> > -- [mdw]

>
> Well, in that case the C containers library will be better than the STL
>
>
>
> Thanks for your very informative message.


Another scheme that's totally portable and relatively clean, even in
C89:

typedef struct basic_container_s {
unsigned flags;
... common fields of basic container functionality
} BASIC_CONTAINER;

typedef struct simple_container_s {
BASIC_CONTAINER base[1];
} SIMPLE_CONTAINER;

typedef struct augmented_container_s {
BASIC_CONTAINER base[1];
OBSERVER observer[1];
... additional fields of a container with augmented functionality
} AUGMENTED_CONTAINER;

/* This may look wierd, but it leads to a correct result. */
typedef BASIC_CONTAINER CONTAINER;

CONTAINER *make_simple_container(void)
{
SIMPLE_CONTAINER *c = safe_malloc(sizeof *c);
c->base->flags = 0;
return c->base;
}

CONTAINER *make_augmented_container(void)
{
AUGMENTED_CONTAINER *c = safe_malloc(sizeof *c);
c->base->flags = AUGMENTED;
return c->base;
}

void set_observer(CONTAINER *c, OBSERVER *o)
{
die_unless(c->base->flags & AUGMENTED);
*((AUGMENTED_CONTAINER)c)->observer = *o;
}

Now,

CONTAINER c = make_simple_container();
CONTAINER d = make_augmented_container();
OBSERVER o[1] = {{ ... observer fields ... }};

set_observer(d, o);
set_observer(c, o); // !!! ERRROR !!!

Essentially this gives you one nice level of subclassing. It doesn't
continue gracefully to more than one level, however. If you need
multiple kinds of augmentation, it may be best to augment with a
single void pointer and hang different data on the pointer as needed.
E.g. Lisp would use a property list.
 
Reply With Quote
 
 
 
 
Chris M. Thomasson
Guest
Posts: n/a
 
      11-23-2010
"Mark Wooding" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ...
[...]

> /* Ensure extension record for the header. Assume single
> * threaded access to the header. This can't be allocated yet.
> */
> if ((xv[i] = malloc(sizeof(struct ext))) == 0)
> return (0);
> h->f |= F_EXT;
> }


I am wondering exactly how can you _assume_ single threaded access to
`xv[i]' here? If you could, then there should be no need for the CAS.
AFAICT, in order for this to work, you would need to use something like:

<quick pseudo-code>
__________________________________________________ ________
#define HEADERS_MAX 64U


struct extension
{
// [...; list of observers; whatever...];
};


struct extension_header
{
struct extension* ext[HEADERS_MAX];
};


struct container_header
{
// [...];
};


struct container_mem_chunk
{
struct extension_header* xhdr; // = NULL
struct container_header hdr[HEADERS_MAX];
// [...];
};


struct extension*
container_header_ensure_extension(
struct container_header* const self
){
struct container_mem_chunk* const chunk =
CHUNK_FROM_HEADER(self);

size_t hdr_idx = self - chunk->hdr;

// conditionally create the extension_header `xhdr'
struct extension_header* xhdr =
ATOMIC_LOAD_CONSUME(&chunk->xhdr);

if (! xhdr)
{
if (! (xhdr = malloc(sizeof(*xhdr)))) return NULL;

struct extension_header* xhdr_cmp =
ATOMIC_CAS_STRONG_ACQ_REL(&chunk->xhdr, NULL, xhdr);

if (xhdr_cmp)
{
free(xhdr);
xhdr = xhdr_cmp;
}
}


// conditionally create the extension `x' specific to the header `self'
struct extension* x =
ATOMIC_LOAD_CONSUME(&xhdr->[hdr_idx]);

if (! x)
{
if (! (x = malloc(sizeof(*x)))) return NULL;

struct extension* x_cmp =
ATOMIC_CAS_STRONG_ACQ_REL(&xhdr->ext[hdr_idx], NULL, x);

if (x_cmp)
{
free(x);
x = x_cmp;
}
}

return x;
}
__________________________________________________ ________


 
Reply With Quote
 
 
 
 
jacob navia
Guest
Posts: n/a
 
      11-23-2010
Le 23/11/10 00:39, Tim Rentsch a écrit :

> Are you going to offer any kind of statement of requirements?
> If not, I suggest the first order of business is to formulate
> one.


What do you mean by that?

Can you explain?

Thanks
 
Reply With Quote
 
Mark Wooding
Guest
Posts: n/a
 
      11-23-2010
"Chris M. Thomasson" <(E-Mail Removed)> writes:

> "Mark Wooding" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) ...
> [...]
>
> > /* Ensure extension record for the header. Assume single
> > * threaded access to the header. This can't be allocated yet.
> > */
> > if ((xv[i] = malloc(sizeof(struct ext))) == 0)
> > return (0);
> > h->f |= F_EXT;
> > }

>
> I am wondering exactly how can you _assume_ single threaded access to
> `xv[i]' here?


Essentially, I'm imposing an obligation on the client to use each
container object in a single threaded way. I inferred this obligation
from Jacob's earlier posting: he complained that a hashtable-based
implementation introduced a requirement for locking. Alternatively, the
container implementation could arrange to lock the header before calling
the function to ensure the extension record. Since `xv[i]' is only
accessed from the single thread working with the ith header in the
chunk, this is sufficient.

> If you could, then there should be no need for the CAS.


I think the CAS is needed to synchronize between different threads using
different headers in the same chunk concurrently, which is permitted.

Does that seem reasonable?

-- [mdw]
 
Reply With Quote
 
Chris M. Thomasson
Guest
Posts: n/a
 
      11-23-2010
"Mark Wooding" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ...
> "Chris M. Thomasson" <(E-Mail Removed)> writes:
>
>> "Mark Wooding" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed) ...


[...]

> Essentially, I'm imposing an obligation on the client to use each
> container object in a single threaded way.


Okay.

[...]


>> If you could, then there should be no need for the CAS.

>
> I think the CAS is needed to synchronize between different threads using
> different headers in the same chunk concurrently, which is permitted.
>
> Does that seem reasonable?


Yes.


 
Reply With Quote
 
Chris M. Thomasson
Guest
Posts: n/a
 
      11-23-2010
"Mark Wooding" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ...
> "Chris M. Thomasson" <(E-Mail Removed)> writes:
>
>> "Mark Wooding" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed) ...


[...]

> Essentially, I'm imposing an obligation on the client to use each
> container object in a single threaded way.


Okay.

[...]


>> If you could, then there should be no need for the CAS.

>
> I think the CAS is needed to synchronize between different threads using
> different headers in the same chunk concurrently, which is permitted.
>
> Does that seem reasonable?


Yes.


 
Reply With Quote
 
ImpalerCore
Guest
Posts: n/a
 
      11-23-2010
On Nov 18, 6:00*pm, jacob navia <(E-Mail Removed)> wrote:
> An observer is a "must have" for my container library.


<snip>

> not
> * * *very exciting considering that in 99.99% of the case you are not
> * * *going to use it.


I have to admit I got a chuckle from your "must have" constraint for
something you would use 0.01% of the time. There is a tradeoff
between utility and complexity, and with those numbers I'd be pretty
confident that this is not a good tradeoff.

But if you want to pursue it for your own curiosity, go for it.

Best regards,
John D.
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      11-23-2010
Le 23/11/10 17:21, ImpalerCore a écrit :
> On Nov 18, 6:00 pm, jacob navia<(E-Mail Removed)> wrote:
>> An observer is a "must have" for my container library.

>
> <snip>
>
>> not
>> very exciting considering that in 99.99% of the case you are not
>> going to use it.

>
> I have to admit I got a chuckle from your "must have" constraint for
> something you would use 0.01% of the time. There is a tradeoff
> between utility and complexity, and with those numbers I'd be pretty
> confident that this is not a good tradeoff.
>
> But if you want to pursue it for your own curiosity, go for it.
>
> Best regards,
> John D.


In most of the multi-threaded programs, 99.99% of the time there aren't
any contention issues and you can spare yourself making a semaphore access.

Problem is, in 0.01% of the cases there IS a contention and you need a
semaphore. Even if you do not need it most of the time having a
semaphore is absolutely essential...

jacob
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      11-23-2010
On 2010-11-23, jacob navia <(E-Mail Removed)> wrote:
> Le 23/11/10 00:39, Tim Rentsch a ?crit :
>> Are you going to offer any kind of statement of requirements?
>> If not, I suggest the first order of business is to formulate
>> one.


> What do you mean by that?


I'm not Tim, but it seemed to me that the first question is what
the specification is. Implementing an observer is not useful unless
users have a clear idea what the observer does. In particular, since
you've proposed that other people might adopt the container library
API, there should be a specification somewhere such that someone else
could implement it, and a user of your library could switch to theirs
(or vice versa) without any code breaking.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.
 
Reply With Quote
 
ImpalerCore
Guest
Posts: n/a
 
      11-23-2010
On Nov 23, 12:35*pm, jacob navia <(E-Mail Removed)> wrote:
> Le 23/11/10 17:21, ImpalerCore a écrit :
>
>
>
> > On Nov 18, 6:00 pm, jacob navia<(E-Mail Removed)> *wrote:
> >> An observer is a "must have" for my container library.

>
> > <snip>

>
> >> * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *not
> >> * * * very exciting considering that in 99.99% of the case you are not
> >> * * * going to use it.

>
> > I have to admit I got a chuckle from your "must have" constraint for
> > something you would use 0.01% of the time. *There is a tradeoff
> > between utility and complexity, and with those numbers I'd be pretty
> > confident that this is not a good tradeoff.

>
> > But if you want to pursue it for your own curiosity, go for it.

>
> > Best regards,
> > John D.

>
> In most of the multi-threaded programs, 99.99% of the time there aren't
> any contention issues and you can spare yourself making a semaphore access.
>
> Problem is, in 0.01% of the cases there IS a contention and you need a
> semaphore. Even if you do not need it most of the time having a
> semaphore is absolutely essential...


Ah, I didn't catch that you intended it for multi-threaded
applications. I thought that you were referring to just needing an
observer pattern out of any context.

I don't have experience with multi-threaded containers, so I have no
ideas to offer.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Implementing the observer pattern in C jacob navia C Programming 3 03-29-2011 06:48 AM
implementing mvc - using observer pattern - beginner to OOP Adam Akhtar Ruby 8 11-11-2008 01:31 PM
Observable, Observer and recursive update() problem Rogan Dawes Java 4 06-11-2004 02:34 PM
Observer/Observable: update not called Timo Nentwig Java 1 04-16-2004 04:21 PM
Why don't Listeners use Observer/Observable Timo Nentwig Java 1 10-27-2003 04:13 PM



Advertisments