I've been working on adding dcrypt to Phobos, which meant
considering what to do in terms of taking it easy and simply
pushing it in as-is, or converting all of the classes and
interfaces into structs with type checkers (I'll be doing the
latter). But it made me consider the pros and cons of the two
options.
Basically, it seemed to come down to:
Pro-structs
1. Smaller, faster
2. Adds unique D-ish flavor to the standard library
Anti-structs
1. Difficult to read. E.g. a beginning programmer needs to be
able to look at this and understand it before he can use the
library:
size_t insertBack(Stuff)(Stuff stuff) if
(isImplicitlyConvertible!(Stuff, T) || isInputRange!Stuff &&
isImplicitlyConvertible!(ElementType!Stuff, T));
And of course, even being able to read it, one would still need
to track down isInputRange() and isImplicitlyConvertible() to
know what they do.
2. When using classes and interfaces, type checking is as simple
as writing the type to be passed in as a parameter. With
struct-typing, people need to manually append a series of checks
all over the place, which results in things like the following:
auto uniform(T, UniformRandomNumberGenerator)(ref
UniformRandomNumberGenerator urng) if (!is(T == enum) &&
(isIntegral!T || isSomeChar!T));
Even though isUniformRNG() exists and is used on other
implementations of uniform(), it isn't used here, because whoever
developed the function forgot to include it on this particular
function.
3. Non-extensible. To "extend" an SList or whatever, I would have
to write a wrapper class with methods that forward to the SList
methods, if I wanted my object to be able to interoperate with
Phobos, or I would need to modify Phobos so that the body of
SList was a template that could be mixed in (assuming I didn't
want to override any methods, just add new ones).
4. Unclear how great an advantage the smaller/faster aspect
actually gives us relative to the demerits of this style of
coding. For example, using code from the below writeup (see
below), I tested the performance of inserting 100,000 items then
removing them all 100 times with both the interface/class and
struct versions, for a total time of 1905±4ms / 1930±10ms (with a
slightly smaller test the struct won, suggesting that there's no
real difference). My suspicion is that the compiler/linker was
detecting that there was only a single implemntation with no
subclasses, hence it compiled out to something roughly equivalent
with no vtable, so I split class implementation of HashSet into
two, with an abstract base class that contained the "data"
variable and nothing else, with all the methods declared in the
subclass and that bumped the runtime to 1980±10ms. But still
that's only a 2.5% difference in speed and only if one goes
gung-ho with layering classes.
And for many objects - like random generators or HashSets - you
aren't going to have masses of instances of the same type, just
one top-level instance that internally contains basic data types
(like structs), so there likely won't be much of a memory
difference for most applications either.
Personally, I think that a better method of type-specialization
needs to be added to the language (e.g. allowing isX!T statements
to be used as types where we write types rather than preprocessor
functions or allowing structs to implement interfaces) so that
post-fixed "if" statements on function declarations are more of a
last-ditch effort, rather than the norm. Though as pointed out,
it might not be worth it unless someone can point out truly
significant performance advantages.
But certainly for the moment, at least having an article about
these things on the top site seems advisable, given how
frequently we see them in the standard library. Plus, users and
Phobos developers might want to have a quick tutorial to make
their own.
So here's a quick write-up:
----
The core library of a language should be small, fast, powerful,
and generic. This last item, however, causes a problem for
library architects. Traditionally, the more generic something is,
the larger and slower it is - with several layers of abstraction
and indirection to allow many disparate implementations of a
generic idea to all serve under the same interface. D supports
all of the features that would allow one to write a library like
this, but it also supports features that allow one to write a
library which does not sacrifice performance for generality.
For example, here would be a standard declaration of a Set
interface and a simple implementation as a class:
interface Set(T) {
size_t length();
size_t insert(T);
T front();
T back();
void removeFront();
void removeBack();
}
class HashSet(T) : Set!(T) {
private:
void[0][T] data;
public:
size_t length() {
return data.length;
}
size_t insert(T value) {
data[value] = [];
return data.length;
}
T front() {
foreach (k, v; data) {
return k;
}
return T.init;
}
T back() {
foreach_reverse (k, v; data) {
return k;
}
return T.init;
}
void removeFront() {
if (data.length == 0) return;
T key;
foreach (k, v; data) {
key = k;
break;
}
data.remove(key);
}
void removeBack() {
if (data.length == 0) return;
T key;
foreach_reverse (k, v; data) {
key = k;
break;
}
data.remove(key);
}
}
When we write a function which accepts a Set, we can write:
void foo(Set someSet) {
someSet.insert(a);
writeln(someSet.front);
}
This will accept and operate on any class which implements the
Set interface (as you would expect).
To reduce overhead, in the D standard library, it is standard to
try and implement this as a struct instead of as a class. But if
we implement HashSet as a struct (which cannot implement an
interface), then we would traditionally have no way to write
functions which can accept generic types, like Sets.
This is solved firstly by use of the templating system. If I have
a function which accepts a templated type, then so long as the
code compiles once the type has been resolved, any arbitrary
class or struct which implements the correct functions will
compile and operate correctly.
void foo(Set)(Set someSet) { // "Set" is just a templated type
name
someSet.insert(a); // Only compiles if Set resolves to a type
with insert and front defined
writeln(someSet.front);
}
In a sense, this is a method for duck-typing in D, though not a
very good one since if we look at the function declaration, it is
not clear what types are or are not valid as parameters to foo().
We must look through the implementation of foo() to find useages
of someSet to determine what is required. Likewise, there is
nothing like "interface Set" which is mandating a standardized
set of methods that all of our functions can expect and which
developers of new implementations of Set types can know to
implement.
This is corrected by use of compile-time duck-type checking
templates. First we declare a template which implements a static
test of compilability of the type for our chosen interface.
template isSet(Set) {
enum bool isSet = is(typeof(
(inout int = 0)
{
Set!int s = void; // can define an instance
if (s.length == 0) {} // can test size
s.insert(1); // can insert
auto h = s.front; // can access front
h = s.back; // can access back
s.removeFront; // can remove front
s.removeBack; // can remove back
}));
}
Following this, we first want to validate that our implementation
is compliant.
struct HashSet(T) {
static assert( isSet!(HashSet!T) );
...
}
We can then upgrade foo() to also require only types which
conform:
void foo(Set)(Set someSet) if (isSet!Set) {
...
}
While more verbose, this sort of duck-typing offers advantages
beyond just speed. As it tests only 'compilability', options open
up to allow flexibility in your definitions. One such example,
the random number generators in std.random are defined so that
they can be treated like InputRange types. Any InputRange is
expected to return whether it is empty or not, but as a random
number generator never becomes empty, in std.random the "empty"
value is a constant (enum) attribute rather than a method.
Another similar benefit is the ability to allow undefined return
types. For example, asymmetric cryptography algorithms should
always generate Public and Private keys, but the values that
comprise those keys is dependent on the algorithm used.
RSAPublicKey and ElGamalPublicKey are basic data structures, not
actionable classes. There is no reason to have a shared base
class or common interface. With D's template-based duck-typing,
one can validate the existence of public/private key accessors
(using "auto" to hold the return values), without caring whether
the return type for different implementations have the same or
even interchangeable types.
