Implementing an observer

[jacob navia]

An observer is a "must have" for my container library.

For each container you should be able to add an "observer" to it, i.e.
adding a function that will be called when the container is modified.
The callback function should receive a lot of information about what is
being changed, but that is another problem.

As far as I see I have two choices.

(1) Add a slot to the header object. This is simple, but it would mean
that this already heavy objects are bigger by sizeof(void *), not
very exciting considering that in 99.99% of the case you are not
going to use it.

(2) Add some global list to the software that would maintain a list
(or hash table) of containers, each with a list of functions that
should be called when it changes. Then, the flags field that is now
mostly empty could be used to flag any container that posesses an
observer. If that flag is set, after any modification the software
would inspect the list of observers and see if this one is in
that list. Problems with this second solution is that it represents
a multi-threaded bottleneck, is much more expensive since the
global observer lists could be quite long.

Has anyone here any better solution?

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

 

[Ian Collins]

An observer is a "must have" for my container library.

For each container you should be able to add an "observer" to it, i.e.
adding a function that will be called when the container is modified.
The callback function should receive a lot of information about what is
being changed, but that is another problem.

I guess the obvious question is why is this a "must have"?

As far as I see I have two choices.

(1) Add a slot to the header object. This is simple, but it would mean
that this already heavy objects are bigger by sizeof(void *), not
very exciting considering that in 99.99% of the case you are not
going to use it.

(2) Add some global list to the software that would maintain a list
(or hash table) of containers, each with a list of functions that
should be called when it changes. Then, the flags field that is now
mostly empty could be used to flag any container that posesses an
observer. If that flag is set, after any modification the software
would inspect the list of observers and see if this one is in
that list. Problems with this second solution is that it represents
a multi-threaded bottleneck, is much more expensive since the
global observer lists could be quite long.

Has anyone here any better solution?

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

It isn't. If you wanted to do this, you could derive privately from a
container and overload the methods that modify the it.

 

[Mark Wooding]

(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.

(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.

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.

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 = malloc(sizeof(struct ext))) == 0)
return (0);
h->f |= F_EXT;
}

/* Done. */
return (xv);
}

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]

 

[jacob navia]

Le 19/11/10 01:48, Ian Collins a écrit :

I guess the obvious question is why is this a "must have"?

Sorry, I forgot to mention the applications.

For instance, you have a list of files in a directory and you want to
be notified when some other process changes it.

You have pointers to some elements of a list and you want to keep them
current with the changes done to the list, avoiding pointers that point
to deleted objects, for instance.


You want to avoid a list getting too long, splitting it when it goes
beyond a threshold.

The applications are numerous. Actually this is a known pattern. See
"Design Patterns" by Gamma/Helm/Johnson/Vlissides, page 293.

It isn't. If you wanted to do this, you could derive privately from a
container and overload the methods that modify the it.

All of them?
Wow, kind of a tough job.

Thanks for your contribution.

 

[jacob navia]

Le 19/11/10 01:48, Mark Wooding a écrit :

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...

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.


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 = malloc(sizeof(struct ext))) == 0)
return (0);
h->f |= F_EXT;
}

/* Done. */
return (xv);
}

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.

jacob

 

[Ian Collins]

Le 19/11/10 01:48, Ian Collins a écrit :

Sorry, I forgot to mention the applications.

For instance, you have a list of files in a directory and you want to
be notified when some other process changes it.

Then you definitely want to provide specialised mutators for the container.

You have pointers to some elements of a list and you want to keep them
current with the changes done to the list, avoiding pointers that point
to deleted objects, for instance.

You can identify which containers invalidate pointers when they (the
containers) are modified. If you require the pointers to remain valid,
use a container that provide the appropriate guarantees.

I'm not sure what you mean by "avoiding pointers that point to deleted
objects".

You want to avoid a list getting too long, splitting it when it goes
beyond a threshold.

That shouldn't be the responsibility of the list, but of the process
that performs the insertion.

The applications are numerous. Actually this is a known pattern. See
"Design Patterns" by Gamma/Helm/Johnson/Vlissides, page 293.

They may appear numerous, but they are specialised. Probably too
specialised to encumber a generic container.

All of them?
Wow, kind of a tough job.

Not at all, there aren't that many (a mere handful) methods that mutate
a container.

If you are also considering mutation of objects within the container,
then you have a different set of problems.

 

[Ian Collins]

Le 19/11/10 01:48, Mark Wooding a écrit :

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...


That is complicated in C.



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.

You could probably perform a similar trick with C++ containers by
including the callback mechanism in the allocator (all C++ container
have a allocator template parameter).

Well, in that case the C containers library will be better than the STL

For a subset of "better" and ignoring the "you don't pay for what you
don't use" rule!

 

[jacob navia]

Le 19/11/10 11:24, Ian Collins a écrit :

You could probably perform a similar trick with C++ containers by
including the callback mechanism in the allocator (all C++ container
have a allocator template parameter).

Probably, but it would be QUITE a development...

For a subset of "better" and ignoring the "you don't pay for what you
don't use" rule!

The idea of Mark would allow to implement this rule. If we only build
things as they are required, we would avoid almost all overhead for
objects that do NOT use this facility.

 

[ld]

An observer is a "must have" for my container library.

For each container you should be able to add an "observer" to it, i.e.
adding a function that will be called when the container is modified.
The callback function should receive a lot of information about what is
being changed, but that is another problem.

As far as I see I have two choices.

(1) Add a slot to the header object. This is simple, but it would mean
     that this already heavy objects are bigger by sizeof(void *), not
     very exciting considering that in 99.99% of the case you are not
     going to use it.

(2) Add some global list to the software that would maintain a list
     (or hash table) of containers, each with a list of functions that
      should be called when it changes. Then, the flags field that is now
      mostly empty could be used to flag any container that posesses an
      observer. If that flag is set, after any modification the software
      would inspect the list of observers and see if this one is  in
      that list. Problems with this second solution is that it represents
      a multi-threaded bottleneck, is much more expensive since the
      global observer lists could be quite long.

Has anyone here any better solution?

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

There isn't an Observer Pattern in the STL and it doesn't fit well
with the STL itself which is more compile-time oriented (templates)
while Observers (C++ Signals or Java Listeners) are more runtime
oriented (messages).

It's usually much better and much simpler to use a notification
center. More flexible (before and after or key-based notification),
faster, less contention (cyclic reference), lazy creation and
notification (priority queue), etc... If you have a MOP (Meta Object
Protocol) and support messages and closures like in COS (or CLOS), the
thing become trivial. A spreadsheet is a typical example of a
notification center.

for C++ examples (Poco):
http://pocoproject.org/docs/Poco.NotificationCenter.html

for C++ signals examples (Boost):
http://www.boost.org/doc/libs/1_45_0/doc/html/signals.html
http://www.boost.org/doc/libs/1_45_0/doc/html/signals2.html (thread
safe)

for an Objective-C examples (Cocoa):
http://developer.apple.com/library/...tifications/Articles/NotificationCenters.html

for Java examples:
http://download.oracle.com/javase/tutorial/uiswing/events/index.html

regards,

laurent

 

[Tim Rentsch]

An observer is a "must have" for my container library.

For each container you should be able to add an "observer" to it,
i.e. adding a function that will be called when the container is
modified.
The callback function should receive a lot of information about what
is being changed, but that is another problem.

As far as I see I have two choices.

(1) Add a slot to the header object. This is simple, but it would mean
that this already heavy objects are bigger by sizeof(void *), not
very exciting considering that in 99.99% of the case you are not
going to use it.

(2) Add some global list to the software that would maintain a list
(or hash table) of containers, each with a list of functions that
should be called when it changes. Then, the flags field that is now
mostly empty could be used to flag any container that posesses an
observer. If that flag is set, after any modification the software
would inspect the list of observers and see if this one is in
that list. Problems with this second solution is that it represents
a multi-threaded bottleneck, is much more expensive since the
global observer lists could be quite long.

Has anyone here any better solution?

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

 

[Gene]

Le 19/11/10 01:48, Mark Wooding a écrit :

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...

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.

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 = malloc(sizeof(struct ext))) == 0)
               return (0);
             h->f |= F_EXT;
           }

           /* Done. */
           return (xv);
         }

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.

 

[Chris M. Thomasson]

[...]

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

I am wondering exactly how can you _assume_ single threaded access to
`xv' 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;
}
__________________________________________________________

 

[jacob navia]

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

 

[Mark Wooding]

[...]

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

I am wondering exactly how can you _assume_ single threaded access to
`xv' 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' 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]

 

[Chris M. Thomasson]

news:[email protected]...

[...]

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.

 

[Chris M. Thomasson]

news:[email protected]...

[...]

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.

 

[ImpalerCore]

An observer is a "must have" for my container library.

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.

 

[jacob navia]

Le 23/11/10 17:21, ImpalerCore a écrit :

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

 

[Seebs]

Le 23/11/10 00:39, Tim Rentsch a ?crit :

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

 

[ImpalerCore]

Le 23/11/10 17:21, ImpalerCore a écrit :







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.