Chris, Bill, All
My mummy tells me not to feed the flames, but...
On 28/01/2011, at 7:38 AM, Chris Suter wrote:
Hi Bill,
On Fri, Jan 28, 2011 at 4:51 AM, Bill Bumgarner <b...@mac.com> wrote:
You have measured a situation where the pattern's marginal slowness
actually
matters?
No, of course not; I don't have a real world use case for it and, I
suspect, neither does anyone else.
... them fighting words.
I wrote an Objective-C wrapper around Graphviz I call "GraphKit". One
of the graph methods is to find the smallest cluster that encloses a
set of nodes. Each cluster may have subclusters. Each cluster has
nodes, but also contains the nodes of its subclusters. This design is
based 1-1 to the Graphviz C API actually.
So the method I wrote is:
- (GKGraph*)clusterForNodes:(NSSet*)nodes
{
__block GKGraph* smallestCluster = nil;
__block BOOL (^findSmallestCluster)(GKGraph*);
findSmallestCluster = ^(GKGraph* cluster)
{
NSMutableSet* directNodes = [NSMutableSet
setWithSet:cluster.nodes];
for (GKGraph* subcluster in cluster.subgraphs)
if (subcluster.isCluster)
{
if (findSmallestCluster(subcluster))
return YES;
[directNodes minusSet:subcluster.nodes];
}
if ([nodes intersectsSet:directNodes])
{
if ([nodes isSubsetOfSet:directNodes])
smallestCluster = cluster;
return YES;
}
else
return NO;
};
findSmallestCluster(self);
return smallestCluster;
}
The findSmallestCluster block captures the smallestCluster local
variable as well as the nodes parameter. The BOOL result is just to
short-circuit further testing -- if any leaf call hits a set
intersection, we don't have to look further.
The equivalent without blocks might look like:
- (BOOL)findSmallestClusterForGraph:(GKGraph*)graph smallestCluster:
(GKGraph**)smallestCluster nodes:(NSSet*)nodes
{
NSMutableSet* directNodes = [NSMutableSet setWithSet:cluster.nodes];
for (GKGraph* subcluster in cluster.subgraphs)
if (subcluster.isCluster)
{
if ([self findSmallestClusterForGraph:subcluster
smallestCluster:smallestCluster nodes:nodes])
return YES;
[directNodes minusSet:subcluster.nodes];
}
if ([nodes intersectsSet:directNodes])
{
if ([nodes isSubsetOfSet:directNodes])
*smallestCluster = cluster;
return YES;
}
else
return NO;
}
- (GKGraph*)clusterForNodes:(NSSet*)nodes
{
GKGraph* smallestCluster = nil;
[self findSmallestCluster:self smallestCluster:&smallestCluster
nodes:nodes];
return smallestCluster;
}
The recursive block allows me to hide the recursion within a method,
also to avoid having to return more than 1 type (BOOL + GKGraph*) from
the recursion i.e. avoiding the ugly GKGraph** smallestCluster
parameter.
On the other hand, the block formulation is not quite in sequence with
how the code actually flows either -- which is one of the advantages
of block programming IMHO. At least the block code is not too far
visually from the invoking code.
The thing about recursion is it forces you to name the recursive part,
in order for recursion to work. At least with blocks I can avoid
polluting the method namespace with the recursion name.
This is shipping or soon-to-be shipping code (Instaviz 2.0).
A Block_copy() is going to often be at least an order of magnitude
(if not
more) slower because it ends up causing a malloc(). Given that
there will
only be one allocation (or one assignment), it is likely that the
overhead
of either will be in the noise.
I was actually hinting at the slowness caused by using a block
variable. I forget exactly how many levels of indirection the block
variable incurs, three perhaps vs. a single call instruction, and
there's no way for the compiler to optimise it.
As you say, it's unlikely to make a difference but if you were to use
tail recursion and have a large number of iterations, then it might.
I thought __block variables are not on the heap until the block itself
is copied?
A smart compiler could see that the block only exists or is used
within a scope, so the __block variable will only ever be on the
stack, so there should only be the single indirection at most? I know
gcc used to solve the aliasing problem within certain scopes so things
like dereferencing a C++ reference would not end up loading from
memory all the time.
I found the Blocks example to be more readable, but to each his own.
When I say readable, I also mean less prone to error. If you forget
the __block type qualifier, you don't get a compiler warning. Also if
you were stupid enough to reuse the block variable later that would
change the behaviour of the earlier block.
You do get an analyzer warning if you forget the __block modifier. It
complains that you are capturing garbage since it is uninitialized.
I wonder if you can do a const __block or some other, um, abomination.
It also smells. Using a block variable to call yourself recursively
is a hack.
I have to agree with you partially. It looks fishy but I don't have
enough experience with blocks so far to outright call it a hack.
I like my original (bad) formulation
BOOL (^findSmallestCluster)(GKGraph*) = ^(GKGraph* cluster) { ... }
better since it is more succinct.
What bugs me is the block being told its own name so to speak. If
there was some way to call the block from within itself e.g.
^(GKGraph* cluster) { ... __self__(subcluster); /* recursive call
*/ ... }
Cheers, Glen Low
---
pixelglow software | simply brilliant stuff
www.pixelglow.com
aim: pixglen
twitter: pixelglow
_______________________________________________
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
