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

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.

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

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

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.

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.

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] ();

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?

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.

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.