View mode: basic / threaded / horizontal-split · Log in · Help
September 26, 2009
Dispatching on a variant
I've had a good poke around the forums and couldn't find anything on this so ...

What's the recommended method for dispatching code off the runtime type of a variant variable
(Phobos D2 std.variant)?

Does one use a bunch of

if ( var.peek!(type1)) { ... }
else if ( var.peek!(type2)  { ... }

for all N possible types, or is there a better & faster way with a switch or jump table of sorts?

Thanks all.

-- Justin Johansson
September 26, 2009
Re: Dispatching on a variant
Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:

> I've had a good poke around the forums and couldn't find anything on
> this so ...
> 
> What's the recommended method for dispatching code off the runtime type
> of a variant variable (Phobos D2 std.variant)?
> 
> Does one use a bunch of
> 
> if ( var.peek!(type1)) { ... }
> else if ( var.peek!(type2)  { ... }
> 
> for all N possible types, or is there a better & faster way with a
> switch or jump table of sorts?

If the type count gets large, how fast it is depends on the backend 
optimizations of the compiler. In the worst case it is a O(n) time linear 
search. A jump table or almost any other way of dispatching would be 
faster. If the variant had an integral tag field, it could be used in a 
switch; that way the compiler could easily optimize it further with the 
currently available constructs.

This problem is solved in higher level languages by providing pattern 
matching constructs. The compiler is free to optimize the code the way it 
likes:

 case var of
   type1 => ...
   type2 => ...
   ...

But since no C-like language has ever implemented pattern matching, it 
might be too radical to add it to D.
September 26, 2009
Re: Dispatching on a variant
Justin Johansson wrote:
> I've had a good poke around the forums and couldn't find anything on this so ...
> 
> What's the recommended method for dispatching code off the runtime type of a variant variable
> (Phobos D2 std.variant)?
> 
> Does one use a bunch of
> 
> if ( var.peek!(type1)) { ... }
> else if ( var.peek!(type2)  { ... }
> 
> for all N possible types, or is there a better & faster way with a switch or jump table of sorts?
> 
> Thanks all.
> 
> -- Justin Johansson

I'd planned to implement visitation for Variant, but never got around to it.

Andrei
September 26, 2009
Re: Dispatching on a variant
language_fan Wrote:

> Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:
> 
> > I've had a good poke around the forums and couldn't find anything on
> > this so ...
> > 
> > What's the recommended method for dispatching code off the runtime type
> > of a variant variable (Phobos D2 std.variant)?
> > 
> > Does one use a bunch of
> > 
> > if ( var.peek!(type1)) { ... }
> > else if ( var.peek!(type2)  { ... }
> > 
> > for all N possible types, or is there a better & faster way with a
> > switch or jump table of sorts?
> 
> If the type count gets large, how fast it is depends on the backend 
> optimizations of the compiler. In the worst case it is a O(n) time linear 
> search. A jump table or almost any other way of dispatching would be 
> faster. If the variant had an integral tag field, it could be used in a 
> switch; that way the compiler could easily optimize it further with the 
> currently available constructs.
> 
> This problem is solved in higher level languages by providing pattern 
> matching constructs. The compiler is free to optimize the code the way it 
> likes:
> 
>   case var of
>     type1 => ...
>     type2 => ...
>     ...
> 
> But since no C-like language has ever implemented pattern matching, it 
> might be too radical to add it to D.

Thanks both for replies.

I've got about 2 dozen types in the variant so the O(n) really hurts.
The variant thing seemed like a really cool idea at the time but now ...
Without something like suggested above or a computed goto on typeid or Andrei's visitator,
it almost pushes me to backout from using variants and having to redesign around some common base class or interface and using virtual function dispatch. :-(
September 26, 2009
Re: Dispatching on a variant
On Sat, 26 Sep 2009 10:36:06 -0400, Justin Johansson  
<procode@adam-dott-com.au> wrote:
> language_fan Wrote:
>
>> Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:
>>
>> > I've had a good poke around the forums and couldn't find anything on
>> > this so ...
>> >
>> > What's the recommended method for dispatching code off the runtime  
>> type
>> > of a variant variable (Phobos D2 std.variant)?
>> >
>> > Does one use a bunch of
>> >
>> > if ( var.peek!(type1)) { ... }
>> > else if ( var.peek!(type2)  { ... }
>> >
>> > for all N possible types, or is there a better & faster way with a
>> > switch or jump table of sorts?
>>
>> If the type count gets large, how fast it is depends on the backend
>> optimizations of the compiler. In the worst case it is a O(n) time  
>> linear
>> search. A jump table or almost any other way of dispatching would be
>> faster. If the variant had an integral tag field, it could be used in a
>> switch; that way the compiler could easily optimize it further with the
>> currently available constructs.
>>
>> This problem is solved in higher level languages by providing pattern
>> matching constructs. The compiler is free to optimize the code the way  
>> it
>> likes:
>>
>>   case var of
>>     type1 => ...
>>     type2 => ...
>>     ...
>>
>> But since no C-like language has ever implemented pattern matching, it
>> might be too radical to add it to D.
>
> Thanks both for replies.
>
> I've got about 2 dozen types in the variant so the O(n) really hurts.
> The variant thing seemed like a really cool idea at the time but now ...
> Without something like suggested above or a computed goto on typeid or  
> Andrei's visitator,
> it almost pushes me to backout from using variants and having to  
> redesign around some common base class or interface and using virtual  
> function dispatch. :-(
>
>
>

Here's an idea. Since you know each type at compile time, you can generate  
the list of methods they implement + a private set of delegates for their  
implementation. Then on assignment of a type, variant would simply assign  
the correct delegate for each supported method and an exception throwing  
delegate for un-supported methods.
September 26, 2009
Re: Dispatching on a variant
Justin Johansson wrote:
> language_fan Wrote:
> 
>> Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:
>>
>>> I've had a good poke around the forums and couldn't find anything on
>>> this so ...
>>>
>>> What's the recommended method for dispatching code off the runtime type
>>> of a variant variable (Phobos D2 std.variant)?
>>>
>>> Does one use a bunch of
>>>
>>> if ( var.peek!(type1)) { ... }
>>> else if ( var.peek!(type2)  { ... }
>>>
>>> for all N possible types, or is there a better & faster way with a
>>> switch or jump table of sorts?
>> If the type count gets large, how fast it is depends on the backend 
>> optimizations of the compiler. In the worst case it is a O(n) time linear 
>> search. A jump table or almost any other way of dispatching would be 
>> faster. If the variant had an integral tag field, it could be used in a 
>> switch; that way the compiler could easily optimize it further with the 
>> currently available constructs.
>>
>> This problem is solved in higher level languages by providing pattern 
>> matching constructs. The compiler is free to optimize the code the way it 
>> likes:
>>
>>   case var of
>>     type1 => ...
>>     type2 => ...
>>     ...
>>
>> But since no C-like language has ever implemented pattern matching, it 
>> might be too radical to add it to D.
> 
> Thanks both for replies.
> 
> I've got about 2 dozen types in the variant so the O(n) really hurts.
> The variant thing seemed like a really cool idea at the time but now ...
> Without something like suggested above or a computed goto on typeid or Andrei's visitator,
> it almost pushes me to backout from using variants and having to redesign around some common base class or interface and using virtual function dispatch. :-(
> 

I see this sort of design in C all the time with event handling, 
although its with unions rather than discriminated unions, the same 
logic applies.

enum EventType {
	Mouse,
	Key,
	Move,
	...
}
struct Event {
	EventType type;
	union {
		MouseEvent mouse;
		KeyEvent key;
		MoveEvent move;
		...
	}
}

void dispatchEvent(const(Event)* event) {
	...
	with(EventType) final switch(event.type) {
	case Mouse: ...
	case Key: ...
	case Move: ...
	...
	}
	...
}

That's the logic with standard unions, you should be able to get 
something similar with variants. It's more code to setup, but you end up 
with a simple jump table from the switch, and final in D makes it easy 
to change EventType without forgetting to update dispatchEvent.
September 26, 2009
Re: Dispatching on a variant
Justin Johansson wrote:

...
> 
> I've got about 2 dozen types in the variant so the O(n) really hurts.
> The variant thing seemed like a really cool idea at the time but now ...
> Without something like suggested above or a computed goto on typeid or
> Andrei's visitator, it almost pushes me to backout from using variants and
> having to redesign around some common base class or interface and using
> virtual function dispatch. :-(

You can use a hash literal as a jump table but it's an unsafe hack and 
probably not performant depending on what you need to do. Maybe it's easier 
still to write the visitation code yourself or generate code with ctfe than 
to redesign to common base classes.

a hash literal works like this, index with the typeid to get a function ptr 
you can call:

Algebraic!(int, Foo) a;
a = 3;
[ typeid(int) : function { writeln("a is int"); },
 typeid(Foo) : function { writeln("a is Foo"); }
] [a.type] ();
September 26, 2009
Re: Dispatching on a variant
On Sat, Sep 26, 2009 at 10:36 AM, Justin Johansson
<procode@adam-dott-com.au> wrote:

> I've got about 2 dozen types in the variant so the O(n) really hurts.
> The variant thing seemed like a really cool idea at the time but now ...
> Without something like suggested above or a computed goto on typeid or Andrei's visitator,
> it almost pushes me to backout from using variants and having to redesign around some common base class or interface and using virtual function dispatch. :-(

Ouch. 2 dozen types? No offense, but that sounds like "you're doing it
wrong." Revising your strategy is probably for the best.

What are you doing, anyway?
September 26, 2009
Re: Dispatching on a variant
Sat, 26 Sep 2009 12:25:23 -0400, Jeremie Pelletier thusly wrote:

> Justin Johansson wrote:
>> language_fan Wrote:
>> 
>>> Sat, 26 Sep 2009 09:32:55 -0400, Justin Johansson thusly wrote:
>>>
>>>> I've had a good poke around the forums and couldn't find anything on
>>>> this so ...
>>>>
>>>> What's the recommended method for dispatching code off the runtime
>>>> type of a variant variable (Phobos D2 std.variant)?
>>>>
>>>> Does one use a bunch of
>>>>
>>>> if ( var.peek!(type1)) { ... }
>>>> else if ( var.peek!(type2)  { ... }
>>>>
>>>> for all N possible types, or is there a better & faster way with a
>>>> switch or jump table of sorts?
>>> If the type count gets large, how fast it is depends on the backend
>>> optimizations of the compiler. In the worst case it is a O(n) time
>>> linear search. A jump table or almost any other way of dispatching
>>> would be faster. If the variant had an integral tag field, it could be
>>> used in a switch; that way the compiler could easily optimize it
>>> further with the currently available constructs.
>>>
>>> This problem is solved in higher level languages by providing pattern
>>> matching constructs. The compiler is free to optimize the code the way
>>> it likes:
>>>
>>>   case var of
>>>     type1 => ...
>>>     type2 => ...
>>>     ...
>>>
>>> But since no C-like language has ever implemented pattern matching, it
>>> might be too radical to add it to D.
>> 
>> Thanks both for replies.
>> 
>> I've got about 2 dozen types in the variant so the O(n) really hurts.
>> The variant thing seemed like a really cool idea at the time but now
>> ... Without something like suggested above or a computed goto on typeid
>> or Andrei's visitator, it almost pushes me to backout from using
>> variants and having to redesign around some common base class or
>> interface and using virtual function dispatch. :-(
>> 
>> 
> I see this sort of design in C all the time with event handling,
> although its with unions rather than discriminated unions, the same
> logic applies.
> 
> enum EventType {
> 	Mouse,
> 	Key,
> 	Move,
> 	...
> }
> struct Event {
> 	EventType type;
> 	union {
> 		MouseEvent mouse;
> 		KeyEvent key;
> 		MoveEvent move;
> 		...
> 	}
> }
> 
> void dispatchEvent(const(Event)* event) {
> 	...
> 	with(EventType) final switch(event.type) { case Mouse: ...
> 	case Key: ...
> 	case Move: ...
> 	...
> 	}
> 	...
> }
> 
> That's the logic with standard unions, you should be able to get
> something similar with variants. It's more code to setup, but you end up
> with a simple jump table from the switch, and final in D makes it easy
> to change EventType without forgetting to update dispatchEvent.

Exactly, this is what I mentioned previously. Isn't it ugly compared to

 type Event = Mouse | Key | Move;

 void dispatchEvent(Event event) {
   match(event) {
     Mouse m => m.squeek();
     Key k => ...
     ...
   }
 }

What's with all the language proposals here? Why hasn't anyone proposed 
this before? This is in fact very helpful - that's why several modern 
languages have adopted it.
September 26, 2009
Re: Dispatching on a variant
Sat, 26 Sep 2009 18:28:52 +0200, Lutger thusly wrote:

> a hash literal works like this, index with the typeid to get a function
> ptr you can call:
> 
> Algebraic!(int, Foo) a;
> a = 3;
> [ typeid(int) : function { writeln("a is int"); },
>   typeid(Foo) : function { writeln("a is Foo"); }
> ] [a.type] ();

A visitor approach might have a bit slower coefficient than the hash, but 
the same time complexity.
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home