[BIOSAL] Causality and ACTION_STOP

Boisvert, Sebastien boisvert at anl.gov
Wed Nov 26 11:58:16 CST 2014 

> From: George K. Thiruvathukal [gkt at cs.luc.edu]
> Sent: Wednesday, November 26, 2014 11:50 AM
> To: Boisvert, Sebastien
> Cc: biosal at lists.cels.anl.gov
> Subject: Re: Causality and ACTION_STOP
> 
> 
> 
> 
> Ok, great, so after a bit of thinking, I'm going to leave my version of hello_acquaintances as is and start working on something new. core_vector is actually a good match for what I'm trying to accomplish in that program. I would still end up having to iterate
>  the keys of the core_map, which wouldn't be faster than working with a vector.

You should use "struct core_set" (basically like core_map, but only keys) for that.

The set could contain items that need attention. Once processed, remote the item.

You can get an item that needs processing (any of them) in O(1) with core_set_iterator,
and delete is also O(1).

Can you send a message on the list for your pull request if you want me to pull ?

> 
> 
> I'm going to plan on working on the ideas I suggested as part of the more interesting example I'm trying to put together, which will also take advantage of actor spawning, etc.
> 
> 
> I think I will use whatever cycles I have today to spend some time on the paper. :)
> 

Yes, the paper needs attention.

> 
> George
> 
> 
> 
> 
> 
> 
> 
> 
> George K. Thiruvathukal, PhD
> 
> Professor of Computer Science, Loyola University Chicago
> 
> Director, Center for Textual Studies and Digital Humanities
> Guest Faculty, Argonne National Laboratory, Math and Computer Science Division
> Editor in Chief, Computing in
>  Science and Engineering (IEEE CS/AIP)
> 
> (w) 
> thiruvathukal.com (v) 773.829.4872
> 
> 
> 
> 
> 
> 
> 
> 
> On Wed, Nov 26, 2014 at 11:33 AM, Boisvert, Sebastien 
> <boisvert at anl.gov> wrote:
> 
> You can use any action specifier as long as the source and the destination agree on it.
> 
> You could use, for instance, ACTION_SUPER_COOL.
> 
> > From: George K. Thiruvathukal [gkt at cs.luc.edu]
> > Sent: Wednesday, November 26, 2014 11:26 AM
> 
> > To: Boisvert, Sebastien
> > Cc: 
> biosal at lists.cels.anl.gov
> > Subject: Re: Causality and ACTION_STOP
> >
> >
> >
> >
> > Ok, I think I am mostly understanding the general idea. I may need you to walk me through this in person next week.
> >
> >
> > So I should have an ACTION_PUSH_DATA and then I can just refer to the same variable (in my case, actors_to_greet) w/o doing an explicit unpack?
> >
> >
> >
> >
> > George K. Thiruvathukal, PhD
> >
> > Professor of Computer Science, Loyola University Chicago
> >
> > Director, Center for Textual Studies and Digital Humanities
> > Guest Faculty, Argonne National Laboratory, Math and Computer Science Division
> > Editor in Chief, Computing in
> >  Science and Engineering (IEEE CS/AIP)
> >
> > (w)
> > 
> thiruvathukal.com (v) 773.829.4872
> >
> >
> >
> >
> >
> >
> >
> >
> > On Wed, Nov 26, 2014 at 11:14 AM, Boisvert, Sebastien
> > <boisvert at anl.gov> wrote:
> >
> > > From: George K. Thiruvathukal [gkt at cs.luc.edu]
> > > Sent: Wednesday, November 26, 2014 10:56 AM
> > > To: Boisvert, Sebastien
> > > Cc:
> > 
> biosal at lists.cels.anl.gov
> > > Subject: Re: Causality and ACTION_STOP
> > >
> > >
> > >
> > >
> > > Seb,
> > >
> > >
> > > In your assembly code, I cannot find where the map that you packed is being unpacked. For completeness, I looked for all references to core_map_unpack in all of biosal:
> > >
> > >
> > > mininuevo:biosal gkt$ grep core_map_unpack $(find . -name '*.[hc]')
> > > ./core/structures/map.c:int core_map_unpack(struct core_map *self, void *buffer)
> > > ./core/structures/map.h:int core_map_unpack(struct core_map *self, void *buffer);
> > > ./genomics/data/coverage_distribution.c:        core_map_unpack(&map, buffer);
> >
> > You got it. coverage_distribution.c contains the script biosal_coverage_distribution.
> >
> >
> > core_map_unpack is called when receiving ACTION_PUSH_DATA.
> >
> >
> >
> > On the sender side:
> >
> > Parallel code path: the message is sent here.
> > assembly_graph_store.c 503
> >     thorium_actor_send(self, customer, &new_message)  (with action specifier ACTION_PUSH_DATA,)
> >
> > customer is assigned here:
> > assembly_graph_store.c 434
> >     customer = concrete_self->customer;
> >
> > concrete_self->customer is set when receiving ACTION_SET_CONSUMER:
> > assembly_graph_store.c 285
> >         concrete_self->customer = customer;
> >
> >
> >
> >
> >
> > >
> > > ./tests/test_map.c:        core_map_unpack(&map2, buffer);
> > >
> > > I can always use the example in test_map.c, but I'm trying to understand how your Spate code is unpacking the coverage_distribution map
> >
> > The sender is a "struct biosal_assembly_graph_store
> > (with script "struct thorium_script biosal_assembly_graph_store_script")
> > and it sends a "struct core_map" to an actor using its name.
> > The sender does not know the script of the destination. It only knows its name.
> >
> > The receiver is a "struct biosal_coverage_distribution" object (with script
> > "struct thorium_script biosal_coverage_distribution_script").
> > It receives a "struct core_map" since the sender packed such a core_map anyway. Any other
> > behavior for this action specifier and for this destination would cause a problem anyway or strange behavior.
> > There is some sort of contract between the source and the destination for the action ACTION_PUSH_DATA.
> >
> > As usual, the source is free to do whatever it wants with the ACTION_PUSH_DATA message since it "controls
> > its destiny". It could for example do nothing at all with the message and just reply with
> > ACTION_PUSH_DATA_REPLY. This is how we get robustness.
> >
> > > (from assembly_graph_store.c, line 494). It would seemingly need to be unpacked somewhere.
> >
> > Yes. I agree.
> >
> > The answer is:
> >
> > coverage_distribution.c in the list you provided.
> >
> >
> > >
> > > George
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > George K. Thiruvathukal, PhD
> > >
> > > Professor of Computer Science, Loyola University Chicago
> > >
> > > Director, Center for Textual Studies and Digital Humanities
> > > Guest Faculty, Argonne National Laboratory, Math and Computer Science Division
> > > Editor in Chief, Computing in
> > >  Science and Engineering (IEEE CS/AIP)
> > >
> > > (w)
> > >
> > 
> thiruvathukal.com (v) 773.829.4872
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > On Wed, Nov 26, 2014 at 10:23 AM, Boisvert, Sebastien
> > > <boisvert at anl.gov> wrote:
> > >
> > > > From: George K. Thiruvathukal [gkt at cs.luc.edu]
> > > > Sent: Wednesday, November 26, 2014 10:11 AM
> > > > To: Boisvert, Sebastien
> > > > Subject: Re: Causality and ACTION_STOP
> > > >
> > > >
> > > >
> > > >
> > > > Hi Seb,
> > > >
> > > >
> > > > See below!
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > On Wed, Nov 26, 2014 at 10:03 AM, Boisvert, Sebastien
> > > > <boisvert at anl.gov> wrote:
> > > >
> > > >
> > > > > I am looking at spate_metagenome_assembler/spate.c but don't see any usage of core_map. I did see a usage of core_map in argonnite.c, but the map is not actually being sent in a message, AFAICT. :)
> > > >
> > > > Spate uses the BioSAL actor library in genomics/
> > > >
> > > > Check out genomics/assembly/assembly_graph_store.c line 494
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > ​This looks like the magic formula! I didn't look too closely at the inclusion list.
> > > >
> > > >
> > >
> > > This is basically the same pattern used in thorium_actor_send_vector.
> > >
> > > So you can just take that as a starting point for thorium_actor_send_map.
> > >
> > > >
> > > >     new_count = core_map_pack_size(&concrete_self->coverage_distribution);
> > > >     new_buffer = thorium_actor_allocate(self, new_count);
> > > >     core_map_pack(&concrete_self->coverage_distribution, new_buffer);
> > > >
> > > >     printf("SENDING %s/%d sends map to %d, %d bytes / %d entries\n",
> > > >
> > > >                         thorium_actor_script_name(self),
> > > >                     thorium_actor_name(self),
> > > >                     customer, new_count,
> > > >                     (int)core_map_size(&concrete_self->coverage_distribution));
> > > >
> > > >     thorium_message_init(&new_message, ACTION_PUSH_DATA, new_count, new_buffer);
> > > >     thorium_actor_send(self, customer, &new_message);
> > > >
> > > >
> > > >     thorium_message_destroy(&new_message);
> > > >
> > > >
> > > >
> > > >
> > > > :-) Thanks!
> > > >
> > > >
> > > >
> > > >
> > > > If we do thorium_message_destroy(), does it also free the underlying buffer?
> > > >
> > > > ​
> > > >
> > >
> > > No.
> > >
> > > thorium_message_destroy() does not free any memory because
> > > thorium_message_init() does not allocate any memory neither.
> > >
> > > I guess this is just because I use to do more C++.
> > >
> > > >
> > > > >
> > > > >
> > > > > I'm planning to add these functions to make sending/receiving maps easy.
> > > >
> > > > That a good idea. I like it.
> > > >
> > > >
> > > >
> > > > ​Great! I will give myself this task. I'm going to end up figuring everything out as part of the new version of hello_acq.c.
> > > >
> > > > I want maps primarily because I am mapping an actor name to its (boolean) status of having been greeted or not.
> > >
> > > This makes sense.
> > >
> > > Also, for your information, core_map can never be full although it uses a hash table for the implementation.
> > >
> > > Here is the hierarchy:
> > >
> > > - core_set is implemented on top of core_map
> > > - core_map is implemented on top of core_dynamic_hash_table (dynamic hash table uses incremental resizing, so it can never be full and
> > >                 all calls are still O(1) because of amortization.)
> > > - core_dynamic_hash_table is implemented on top of core_hash_table (hash_table uses double hashing / open addressing)
> > > - core_hash_table is implemented on top of core_hash_table_group (right now, there is 1 group per table, but this could be use to
> > >                 implement a sparse container like in Google Sparse Hash Table based on Donald Knuth's algorithm for that).
> > >
> > > >
> > > > ​
> > > >
> > > >
> > > > > Similar to your view, I think lists and maps are among the most important collections.
> > > >
> > > > There is the free_list structure, but it is only used in memory management right now.
> > > >
> > > > > I once read a paper that most of the reuse in OOP comes from lists and associative structures.
> > > >
> > > > When you say lists, does that include vector. Usually, vector means array and list means
> > > > linked list.
> > > >
> > > >
> > > >
> > > > ​Yes, it does in an evolutionary sense. I tend to think of vector and lists as being connected. In modern programming libraries, you often see the interfaces conflated (i.e. lists have array-like interfaces and vice versa). Java Vector is kind of an interesting
> > > >  case study!
> > >
> > > But a Java ArrayList<Integer> has O(1) random access but can trigger a resize of capacity on insertion which is O(n).
> > >
> > > A Java LinkedList<Integer> has O(n) random access but has O(1) insertion.
> > >
> > > Sure, both implement the List<Integer> interface, but each has a better use case anyway.
> > >
> > >
> > > >
> > > >
> > > > ​TTYL,
> > > > George
> > > >
> > > >
> > > >
> > >
> > >
> > >
> > >
> >
> >
> >
> >
> >
> 
> 
> 
> 
>

More information about the BIOSAL mailing list