Re: Immutable data structures - performance && thoughts
On May 12, 8:31 pm, Marinca Gheorghe wrote:
I recently looked over how a C# library could implement an immutable
stack, and came up with this implementation in C++.
I think the appeal to "immutable datastructures" in languages that
tend to force a level of indirection onto you (well, C# also has
"value types" (to use their terminology) that don't do this) is higher
than in languages like C++ where you only get an indirection when you
ask for it and where class-type objects can be held directly just like
int values in varibles. It seems to me that the idea of "immutable
datastructures" is a way to combine sharing with what we call in the C+
+ community "value semantics". If you have a handle to an object but
the object will never change its state then it does not really make a
difference whether you think of the handle as some kind of pointer or
actually a variable storing the object itself because sharing the same
object is free of surprizes in that case. AFAIK C# and Java do this
with their respective string type. You can treat the reference to a
string as the string itself and copy it efficiently (share the
immutable object).
In C++ you have lots of options to go about organizing your custom
data structure. Value semantics is encouraged. But that does not stop
you from implementing certain things using techniques such as COW
(copy-on-write). In your case the use of std::shared_ptr makes things
easy. But there is an issue I see in combination with linked lists:
struct int_stack_node {
int value;
shared_ptr<int_stack_node> below;
};
class int_stack {
public:
bool empty() const {return !top;}
int top() const;
void push(int value);
void pop();
private:
shared_ptr<int_stack_node> top;
};
void int_stack::push(int value) {
auto sp = make_shared<int_stack_node>();
sp->value = value;
sp->below = move(top);
top = move(sp);
}
void int_stack::pop() {
assert(!empty());
top = top->below;
}
Here, when an int_stack object is destructed it could lead to a lot of
recursive invocations of int_stack_node destructors. So, there is the
danger of a stack overflow.
You might want to think about writing your own smart pointer "cow_ptr"
that provides read-only as well as read/write access like this:
cow_ptr<int> p (construct, 23); // tagged forwarding constructor
cow_ptr<int> q = p;
cout << *p << endl; // read-only access, prints 23
cout << *q << endl; // read-only access, prints 23
assert(&*p == &*q); // still sharing
p.write() = 42; // write-access
cout << *p << endl; // read-only access, prints 42
cout << *q << endl; // read-only access, prints 23
assert(&*p != &*q); // not sharing anymore
The beauty of COW is that you can combine sharing with "value
semantics". If there is no sharing going on, there is no problem of
modifying your list nodes' values, for example. COW made some of Sean
Parents code he showed in his "Value Semantics and Concept-Based
Polymorphism" talk really simple. It's easy to reason about due to
value semantics and efficient due to sharing -- at least if you like
to keep a history of different states allowing the user to press an
UNDO button etc. (You'll find it on Youtube.)
I wonder here
mostly about the overhead of std::shared_pointer(and the missing of a
garbage collector that probably could help for this kinds of
structures)
A garbage collector (instead of shared_ptr) would solve the potential
stack overflow problem here. But it also opens up other issues.
namespace immutable
{
template<typename T>
class stack: public std::enable_shared_from_this<stack<T>>
{
public:
typedef std::shared_ptr<T> headPtr;
typedef std::shared_ptr<stack<T>> StackPtr;
private:
template <typename T> friend struct stackBuilder;
public:
static StackPtr empty()
{
return std::make_shared<stackBuilder<T>>(nullptr, nullptr);
}
static StackPtr Create()
{
return empty();
}
StackPtr push(const T& head)
{
return std::make_shared<stackBuilder<T>>(std::make_shared<T>(head),
shared_from_this());
}
StackPtr pop()
{
return this->tail;
}
headPtr peek()
{
return this->head;
}
bool isEmpty()
{
return (this->head == nullptr);
}
private:
stack(headPtr head, StackPtr tail): head(head), tail(tail)
{
}
stack<T>& operator= (const stack<T>& other);
private:
headPtr head;
StackPtr tail;
};
Why the indirection for the actual T values? It does not seem
necessary. Also, peek should not return a pointer with which the user
could violate the immutability. This breaks value semantics.
How would you think on implementing a general purpose stack in C++ ?
I'd prefer a vector-based stack. And if it turns out that for some
specific application the cost of copying vectors is too big, and move
semantics does not help much, I'd think about writing something like
this:
template<class T>
struct scs_node
{
vector<T> segment_data;
cow_ptr<scs_node> below;
};
template<class T>
class segmented_cow_stack
{
public:
...
...
private:
cow_ptr<scs_node> top;
};
(assuming cow_ptr is a smart pointer described earlier that is move-
enabled to keep the reference counter values small to avoid
unnecessary copying).
There is actually no harm in supporting mutation for "value semantics"-
based types. You don't have to create new segmented_cow_stack<>
objects if you don't want to. But you CAN copy them and then it's like
they don't share their data because mutating one won't have any
observable effect on the other stacks. So, it's not really necessary
to stick to the interface that Eric Lippert suggested in his C#
article.
Cheers!
SG
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]