You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucy.apache.org by Marvin Humphrey <ma...@rectangular.com> on 2012/09/08 04:48:29 UTC
[lucy-dev] Fragile base class problem, revisited
Greets,
A few months back, I attempted to tackle Clownfish's "fragile base class"
problem with regards to instance variables, using techniques inspired by
classic implementations of multiple inheritance in C++. Nick Wellnhofer
objected to the proposal's complexity, among other things:
http://s.apache.org/cTL
All things considered, I'm not sure if prepending the data of subclasses
in front of the object is worth all the trouble.
I'd like to offer Nick belated thanks for his critique, and try again. :) I
continue to believe that fixing this issue is an imperative for Clownfish. It
is not acceptable for users who install a new version of Lucy from CPAN to
have to track down compiled extensions to Lucy and rebuild them. We've
already solved the hardest ~75% of the fragile ABI issue with our vtable and
method dispatch design -- let's finish the job!
Here is an article explaining how the problem was addressed in Objective C
2.0:
http://cocoawithlove.com/2010/03/dynamic-ivars-solving-fragile-base.html
The "modern" Objective-C runtime therefore requires that accessing an ivar
follows this modified approach:
1. Add the offset for the subclass' instance value area to the object's
pointer value
2. Add the offset from the subclass' instance area to the ivar
3. Dereference (read or write from) the memory location referred to by
the offset pointer value
Here's Wikipedia's explanation of C#'s approach:
http://en.wikipedia.org/wiki/Fragile_binary_interface_problem#Languages
Another solution is to write out an intermediate file listing the offsets
and other information from the compile stage, known as meta-data. The
linker then uses this information to correct itself when the library is
loaded into an application. Platforms such as .NET do this.
Both languages are doing something similar to what Clownfish does with its
method OFFSET variables (and quite different from C++), suggesting a direction
for us to explore. Here's a proof of concept[1] in which we define a macro[2]
`Foo_num(self)` which allows access to a member variable `num` of type
`int` as both an lvalue and an rvalue:
static inline void*
SI_member_address(void *self, size_t offset) {
return (char*)self + offset;
}
typedef struct Foo Foo;
#pragma GCC visibility push(hidden)
extern size_t Foo_num_OFFSET;
#pragma GCC visibility pop
#define Foo_num(self) \
(*((int*)SI_member_address(self, Foo_num_OFFSET)))
void
Foo_set_num(Foo *self, int num) {
Foo_num(self) = num;
}
int
Foo_get_num(Foo *self) {
return Foo_num(self);
}
I can think of at least three drawbacks to this approach.
First, we must continue to compile with `-fno-strict-aliasing` and forego the
optimizations it enables.
Second, using variable offsets instead of constant offsets makes each member
var access marginally less efficient. Since we can calculate these offsets at
load time and after that they never change, it seems like we ought to be able
to exploit that information -- but maddeningly, I have not yet figured out a
way.
Third, the macro syntax is a tad verbose and awkward (moreso in lvalue
context)...
self->num = num; // now
Foo_num(self) = num; // proposed
... and it would also require extensive superficial changes to the Lucy core
codebase to switch all direct struct access over to the macro form. :\
There's an alternative: change the meaning of `->` for Clownfish objects in
our .c files (which would no longer be true C as a result). That would
require writing a parser which understands C, which is doable, but ambitious.
If we take this route, I think we could actually stop creating C struct
definitions for Clownfish classes and use the macros for all access. Not that
that's crucial, but it's funny (and instructive) to think that our opaque
structs would be opaque everywhere.
Thoughts?
Marvin Humphrey
[1] See also LUCY-234: http://s.apache.org/bqi
[2] These macros would be parcel-scoped, to avoid the trap of inheritance
breaking encapsulation.
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nick Wellnhofer <we...@aevum.de>.
On 09/09/2012 21:05, Marvin Humphrey wrote:
>> void
>> Sub_method(void *self) {
>> Sub_MEMBERS *members = Sub_get_members(self);
>> members->sub_num = 1;
>> members->sub_float = 1.0;
>>
>> // Only safe if Base is in the same parcel
>> Base_MEMBERS *base_members = Base_get_members(self);
>> base_members->base_num = 1;
>> base_members->base_float = 1.0;
>> }
>
> I'd originally thought to avoid this approach because of the extra line of
> code, but perhaps it's not so bad after all. Plus, there's an idiom for
> single line access;
>
> void
> Foo_set_num(Foo *self, int num) {
> Foo_MEMBERS(self)->num = num;
> }
Yes, I think we can live with that extra line.
> Bikeshedding questions: MEMBERS, or IVARS? Or both? Or something else?
>
> `IVARS` -- an abbreviation of "instance variables" saves two letters. (Also
> FWIW, in Java and C++ both "class variables" and "instance variables" are
> "member variables" -- so "members" is a superset.)
I like 'IVARS'. It seems to come from Objective-C and AFAICS our
solution is similiar to the one of the modern Objective-C runtime.
> void
> Sub_method(void *self) {
> Sub_IVARS *ivars = Sub_MEMBERS(self);
> ivars->sub_num = 1;
> ivars->sub_float = 1.0;
>
> // Only safe if Base is in the same parcel
> Base_IVARS *base_ivars = Base_MEMBERS(self);
> base_ivars->base_num = 1;
> base_ivars->base_float = 1.0;
> }
>
> `Sub_get_members` bothers me because it doesn't use the all caps convention
> which we've informally reserved and therefore looks like userland code.
> (`Foo_num` bothers me for the same reason.) Also the underscore in the type
> name "Sub_MEMBERS" bothers me, but I guess SubMEMBERS isn't a good
> alternative.
I don't like mixing 'IVARS' and 'MEMBERS', but I don't have a strong
opinion on symbol names.
>> The biggest drawback I can see is that objects become void pointers, and
>> we'll lose some of the type-checking that the C compiler currently performs
>> for us. But that's something other solutions to the fragile base class
>> problem will also have to deal with.
>
> Is using void pointers really mandatory? I'm not seeing it.
>
> I think we can continue to use struct types for classes. We still get the
> type checking benefits even if we never define the struct layout and leave the
> type opaque.
Yes, of course. I wasn't thinking clearly.
Nick
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
More muddled thinking on my part. I started with one approach, then
mentally veered into another. If we're presuming multiple layers of
inheritance across more than two shared objects, the struct size of
each object needs to be available as a symbol as well. And I think
the offsets need to be chained.
And we probably need another untouchable struct defined per object.
And of course I should have been using size_t for all the offsets and sizes.
size_t __sizeof_Parent = sizeof(Parent);
struct __just_Child {
int result;
int subfield;
}
// symbols in shared object set to values at library compile time
size_t __Child_id = __Parent_id;
size_t __Child_type = __Parent_type;
size_t __Child_field = __Parent_field;
size_t __Child_order = __Parent_order;
size_t __Child_number = __sizeof_Parent + offsetof(struct __just_Child, number);
size_t __Child_subtype = __sizeof_Parent + offsetof(struct
__just_Child, subtype);
This then brings up packing and padding issues for the struct sizes,
but I'm hoping that this can be solved with appropriate attributes.
Speaking of attributes, I'm presuming that all these symbols for the
main lib will be "protected", so that access within the core won't be
as hindered.
Or perhaps we can simply the the macro act differently when in Core,
and behind the scenes convert to straight struct access.
Speaking of variants on the macro, I'm assuming that there will be
several compile time variants of the macro based on some defines.
Optimized but fragile for non-distributed binaries:
#define Child(self, var) self->var
Speedy but indirect as above:
#define Child(self, var) ( \\
(typeof( ((struct __Child *)0)->var)) \\
((char *) self + __Child_ ## var) \\
)
Debug with safety checks:
Add ISA() checks and anything else we can think of to either of the above.
----
I should mention that part of my confusion as to the need for this is
that I had been presuming that most people compiling their own
extensions would compile the library from source as well. And I
presumed that most people distributing extensions would distribute
source, whether for C or for an interpreted host language.
Could you explain the ecosystem you see existing? Is there a
comparable project that has a distribution style you'd like to
emulate? Just for Linux, I'd think it would be hard to do the
interchange between all minor variations: 32 vs 64 bit, glibc
versions, etc. How many would you envision, and how would the
extensions fit into this system?
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
Already spotted the first of likely many errors in my example:
> typedef struct {
> void[sizeof(struct __Child)] *direct_access_not_allowed;
> } Child_t;
I think this can just be "Child", as the macro Child() and type Child
shouldn't conflict.
> else {
> MyChild(self, result) = self->type[self->number];
> }
>
> return self->id;
> }
Oops, forgot to finish editing after I cut-and-paste my example:
int MyChild_prepare_result(MyChild *self) {
if (MyChild(self, field) == 1 && MyChild(self, subfield) == 2) {
MyChild(self, result) = MyChild(self, order);
}
else {
MyChild(self, result) = MyChild(self, type)[MyChild(self,number)];
}
return MyChild(self, id);
}
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
On Tue, Sep 25, 2012 at 12:19 PM, Marvin Humphrey
<ma...@rectangular.com> wrote:
> If instance variables are hidden by default, that forces users to go through
> the accessor, yielding correct behavior 100% of the time.
>
> That this was not obvious illustrates how different our perspectives and
> priorities are. :(
Happily, I do find this statement obvious. If we need an accessor
method because we are doing some sort of lazy evaluation, it should be
used. But you may be right about the difference in perspectives.
The question is whether we ever want to allow direct access to
instance variables, from inside or outside a parcel. I'd be happy
with disallowing out-of-hierarchy access, and probably OK with a
default of privacy, but don't like not being able to allow direct
access. I don't think we'd be well served by having user defined
subclasses always have less access than the core classes.
Blurring the distinction between the two forces us to have a API,
since we're forced to use it ourself. I think the philosophical
difference is that I'd be comfortable with distinguishing in-class
from out-of-class, but don't like privileging by parcel. I also don't
like the idea of requiring accessors unless they serve a useful
purpose, as in the case you describe.
>> To focus on something specific, consider Peter's custom scoring demo:
>> http://www.mail-archive.com/dev@lucy.apache.org/msg00249.html
>>
>> What would it take to write this as a compiled extension rather than
>> an interpreted one?
>
> If Peter modifies that demo to use composition instead of inheritance, it gets
> a lot simpler and does not require access to instance variables at all.
That's certainly the manner I would prefer, and might work for the
specific case of the demo, but I don't see how that is possible in
general. Perhaps you could remake his demo in that manner once the
API settles?
> If Peter leaves it as a subclass of TermQuery, though, the copied-and-pasted
> code for calculating TFIDF weights remains a nightmare regardless of whether
> vars are accessed directly or via accessors.
We're back to agreement! Yes, it's an injection framework that would
solve this, not direct access to instance vars. :)
> I don't know. I feel like we are very, very far apart on the question of
> information hiding[1], and I don't think either of us is going to make any
> headway persuading the other. We may or may not end up going in circles, but
> we will be off-track for a long time.
OK, I'll drop it here. I've registered my uneasiness, and if it's
unconvincing then proceeding with Nick's proposal is probably the best
plan.
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Mon, Sep 24, 2012 at 10:28 PM, Nathan Kurz <na...@verse.com> wrote:
> On Mon, Sep 24, 2012 at 3:09 AM, Nick Wellnhofer <we...@aevum.de> wrote:
>> I think we're going a bit in circles here.
>
> Not exactly circles. I suggesting that we go back to the last fork
> and check our map, so that we're sure that we're on the right road.
I don't know. I feel like we are very, very far apart on the question of
information hiding[1], and I don't think either of us is going to make any
headway persuading the other. We may or may not end up going in circles, but
we will be off-track for a long time.
> [from earlier]
>> Note that my approach doesn't work with cross-parcel access of member
>> variables, not even with accessing member vars of superclasses if the
>> superclass comes from another parcel. But I think that's something we could
>> live with.
>
> I don't see this as acceptable, although both you and Marvin seem to
> view it as partially a positive.
Right, because it improves encapsulation.
>From _Design Patterns_:
Because inheritance exposes a subclass to details of its parent's
implementation, it's often said that "inheritance breaks encapsulation".
A classic example: lazy loading.
int
Base_get_doc_id(Foo *self) {
if (!self->up_to_date) {
self->doc_id = Base_calculate_doc_id(self);
}
return self->doc_id;
}
If a subclass accesses `doc_id` directly rather than going through
Base_get_doc_id(), it will get the wrong number.
If instance variables are hidden by default, that forces users to go through
the accessor, yielding correct behavior 100% of the time.
That this was not obvious illustrates how different our perspectives and
priorities are. :(
> My feelings come from two separate
> directions:
>
> 1) While this might be acceptable for Lucy, if we were treating
> Clownfish as a separate project I think this would leave it dead in
> the water. I don't think that a general purpose object hierarchy
> system would be well served by not allowing a user defined child class
> to have easy access to the class it inherits from.
If you are writing a class that is designed to be subclassed, it's not a big
deal to provide some accessors.
Even better, focus on interface design rather than code reuse when designing
the superclass. If you can achieve your goals without instance variables or
non-abstract methods, that greatly reduces the problem of inheritance
breaking encapsulation.
> To focus on something specific, consider Peter's custom scoring demo:
> http://www.mail-archive.com/dev@lucy.apache.org/msg00249.html
>
> What would it take to write this as a compiled extension rather than
> an interpreted one?
If Peter modifies that demo to use composition instead of inheritance, it gets
a lot simpler and does not require access to instance variables at all.
If Peter leaves it as a subclass of TermQuery, though, the copied-and-pasted
code for calculating TFIDF weights remains a nightmare regardless of whether
vars are accessed directly or via accessors.
Marvin Humphrey
[1] http://en.wikipedia.org/wiki/Information_hiding#Example_of_information_hiding
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
On Mon, Sep 24, 2012 at 3:09 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> I think we're going a bit in circles here.
Not exactly circles. I suggesting that we go back to the last fork
and check our map, so that we're sure that we're on the right road.
> Your proposal looks very much
> like Marvin's proposal in the first message of this thread (one offset
> global per ivar).
Yes, but more built out version with hopefully more safety and
usability. Both are still broad strokes.
> If you're only concerned with making access of parent class ivars more
> convenient, we could achieve this with a couple of macros on top of my
> proposal:
>
> #define Sub_sub_num(self) Sub_GET_IVARS(self)->sub_num
> #define Sub_sub_float(self) Sub_GET_IVARS(self)->sub_float
> #define Sub_base_num(self) Base_GET_IVARS(self)->base_num
> #define Sub_base_float(self) Base_GET_IVARS(self)->base_float
I'm not only concerned with that, but yes, this would be much better
than not having them. If we take your path, I'd want to add these.
It's really the base assumptions that concern me more. I'll try to
stick to one at a time for a bit.
[from earlier]
> Note that my approach doesn't work with cross-parcel access of member variables, not even with
> accessing member vars of superclasses if the superclass comes from another parcel. But I think
> that's something we could live with.
I don't see this as acceptable, although both you and Marvin seem to
view it as partially a positive. My feelings come from two separate
directions:
1) While this might be acceptable for Lucy, if we were treating
Clownfish as a separate project I think this would leave it dead in
the water. I don't think that a general purpose object hierarchy
system would be well served by not allowing a user defined child class
to have easy access to the class it inherits from.
2) I don't think it works well for Lucy either. I think the main way
people will write compiled extensions is to subclass an existing
scorer, matcher, or posting format. I think discouraging access to
instance variables will make this task much harder than it needs to
be, and force them to copy-and-edit entire class hierarchies.
To focus on something specific, consider Peter's custom scoring demo:
http://www.mail-archive.com/dev@lucy.apache.org/msg00249.html
What would it take to write this as a compiled extension rather than
an interpreted one? I think that almost everything that is done would
benefit from having the same level of access to instance variables as
the parent. Why do we want to discourage this, and what would the
alternative be?
My hope is that user defined extensions can operate at the same level
of efficiency as the core, and that over time we can "de-privilege"
the core classes so that improvements to each are shared. I don't see
what we gain by making this distinction greater. Or is the intent to
discourage such access within the core distributed classes as well?
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Mon, Sep 24, 2012 at 3:09 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> We also want to discourage writing code that relies on access to ivars of
> parent classes. Unless it's a really performance-critical part, I'd rewrite
> the method above to use accessors:
One possibility we might consider is facilitating subclass access to the
instance variables of same-parcel ancestors, by adding those instance
variables to the subclass struct.
To illustrate, these class definitions...
parcel Foo;
class Base {
int a;
}
...
parcel Bar;
class Parent inherits Base {
int b;
}
...
parcel Bar;
class Child inherits Parent {
int c;
}
... would yield the following IVARS struct definitions:
struct Foo_Base_IVARS {
int a;
}
struct Bar_Parent_IVARS {
int b;
}
struct Bar_Child_IVARS {
int b;
int c;
}
Arguably, this encourages "inheritance abuse" -- i.e. tight coupling between
parent and child classes -- but only within the confines of a single parcel,
which is a lot less harmful than tight coupling between classes in different
parcels. (I tend to believe that the parcel is the right level of abstraction
for code reuse anyway.) And I think this simplification -- that you only need
to think about a variable's type and not its ancestry when obtaining the
relevant IVARS struct -- addresses at least some of the concerns that Nate
raises.
> It's just a guess, but I think in most cases the global offset can be
> fetched from L1, so the performance hit should only be around 5 cycles per
> method call (double that if we have to go through the GOT). It's the same
> performance hit that we already take for virtual method dispatch. There will
> be added register pressure though, which might be noticable on x86-32.
FWIW, we achieved consensus a while back that we would optimize for 64-bit and
only concern ourselves with compatibility for 32-bit. That informal agreement
hasn't been documented anywhere, but I still think it's a good policy.
Marvin Humphrey
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nick Wellnhofer <we...@aevum.de>.
On 24/09/2012 08:06, Nathan Kurz wrote:
> 2. Nick's proposal
> We're defining terms differently here. Yes, the proposal is very
> straightforward. The "cognitive load" is that the user needs to be
> aware of not only the object as it is, but the full hierarchy. Or am
> I misunderstanding how things would work?
Your understanding is correct.
> Let me flesh out your example with some silly worst-case pseudocode:
>
> Classes:
>
> class Base {
> int id;
> int *type;
> }
>
> class Parent inherits from Base {
> int field;
> int order;
> }
>
> class Child inherits from Parent {
> int number;
> int subtype;
> }
>
> class MyChild inherits from Child {
> int result;
> int subfield;
> }
> NickNew:
>
> int MyChild_prepare_result(MyChild *self) {
> Base *base_ivars = Base_IVARS(self);
> Parent *parent_ivars = Parent_IVARS(self);
> Child *child_ivars = Child_IVARS(self);
> MyChild *mychild_ivars = MyChild_IVARS(self);
>
> if (parent_ivars->field = 1 && mychild_ivars->subfield == 2) {
> mychild_ivars->result = child_ivars->order;
> }
> else {
> mychild_ivars->result = base_ivars->type[parent_ivars->number];
> }
>
> return base_ivars->id;
> }
>
> I think this matches what is proposed? If so, even the scrolling back
> and forth to get this example right was painful. If it involved
> flipping back and forth between 4 different files (3 of which are
> unfamiliar) it would be excruciating.
> Along that lines, I think I left at least one error in "New" -- how
> long does it take to spot it?
I think your example is a bit extreme. In many methods we'll only access
the ivars of a single class, and I guess that there are only very few
cases where we need access to more than two classes.
We also want to discourage writing code that relies on access to ivars
of parent classes. Unless it's a really performance-critical part, I'd
rewrite the method above to use accessors:
int MyChild_prepare_result(MyChild *self) {
MyChild_IVARS *ivars = MyChild_IVARS(self);
if (MyChild_field(self) == 1 && ivars->subfield == 2) {
ivars->result = MyChild_order(self);
}
else {
int *type = MyChild_type(self);
ivars->result = type[MyChild_number(self)];
}
return MyChild_id(self);
}
> My second "complaint" is that despite this, we still end up with base
> classes that are quite fragile. The benefit (and it is significant)
> is that we gain the ability to add member variables to the end of the
> structs for each parent class. But programmer discipline is needed,
> for if they are added elsewhere compiled modules will break even
> though the local recompile works just fine. Moving a variable from
> Grandparent to Parent causes the same problems. Deletion is always
> going to be tricky, but it would be nice to get an error message
> rather than a segfault. If we are going down this route, I think we
> should aim for truly robust rather than just less fragile.
Note that my approach doesn't allow access to ivars of other parcels. So
within a parcel, we can move and even delete ivars at will.
> On the bright side, I don't think that performance is going to be that
> big of an issue. Maybe 50 cycles per function for the accessing a
> variable once the lookups are cached in L3? Another dozen for the
> pipeline to finish adding the offsets? Repeated access should be much
> faster, and we can easily cache a local pointer for tight loops.
> Taking a blind stab, maybe 25% initially which we can reduce to 10% by
> hitting a few hotspots? Making it fast again while gaining the
> flexibility seems like a fun challenge.
It's just a guess, but I think in most cases the global offset can be
fetched from L1, so the performance hit should only be around 5 cycles
per method call (double that if we have to go through the GOT). It's the
same performance hit that we already take for virtual method dispatch.
There will be added register pressure though, which might be noticable
on x86-32.
> 3. Alternative Proposal
I think we're going a bit in circles here. Your proposal looks very much
like Marvin's proposal in the first message of this thread (one offset
global per ivar).
If you're only concerned with making access of parent class ivars more
convenient, we could achieve this with a couple of macros on top of my
proposal:
#define Sub_sub_num(self) Sub_GET_IVARS(self)->sub_num
#define Sub_sub_float(self) Sub_GET_IVARS(self)->sub_float
#define Sub_base_num(self) Base_GET_IVARS(self)->base_num
#define Sub_base_float(self) Base_GET_IVARS(self)->base_float
If I understand your proposal correctly, this should result in basically
the same compiled code.
Nick
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
It's sad when you write a response and then feel that a Table of
Contents might help to get your readers all the way to the bottom.
But probably worse not to have one if it's presence would help
overcome the reluctance.
1. Friendly Opening
a. Bad Joke
b. General Agreement
c. Tread Softly
2. Nick's Proposal
a. Cognitive Load Defined
b. Revised Example
c. Hierarchy Dependent
d. Error Reporting Suboptimal
e. Still Fragile
f. Performance Acceptable
3. Alternate Proposal
a. Sketchy Code
b. Example Syntax
c. Biased Assessment
f. Restated Requirements
e. Hope for Future
---
1. Friendly Opening
On Sat, Sep 22, 2012 at 3:29 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
> We're at an impasse, then. I'm fundamentally opposed to publishing a
> Clownfish C API where all instance variables are exposed as struct members.
That's an easy one. I'll just try to curl up into a very small ball
so it's not hard for the rest of you to easily step over my dead body.
:)
I actually don't disagree that this is a great thing for Clownfish ---
it's the necessity for Lucy that I'm questioning. Were Clownfish an
independent project, this would be a wonderful direction to go. But
since they are entwined, and since you feel strongly that it's needed
now, the obvious answer is that we do as you say, avoid straight
structs, and come up with the best non-fragile base class system that
we can.
Nick: Let my start by saying your proposal is great! I think there's
room for improvement, but having a proposal on the table makes it a
lot easier to talk about the details.
2. Nick's proposal
>>> The proposal on the table isn't any more complicated than a struct. The way
>>> the fields are laid out in memory is identical.
>>
>> While the second sentence is true, I strongly disagree with the first.
>> The cognitive load is extreme.
>
> I don't think that Nick's proposal is hard to understand. Member variables
> are still accessed via a struct; the interface change is that you have to look
> up that struct first.
We're defining terms differently here. Yes, the proposal is very
straightforward. The "cognitive load" is that the user needs to be
aware of not only the object as it is, but the full hierarchy. Or am
I misunderstanding how things would work?
Let me flesh out your example with some silly worst-case pseudocode:
Classes:
class Base {
int id;
int *type;
}
class Parent inherits from Base {
int field;
int order;
}
class Child inherits from Parent {
int number;
int subtype;
}
class MyChild inherits from Child {
int result;
int subfield;
}
Old:
int MyChild_prepare_result(MyChild *self) {
if (self-->field == 1 && self->subfield == 2) {
self->result = self->order;
}
else {
self->result = self->type[self->number];
}
return self->id;
}
NickNew:
int MyChild_prepare_result(MyChild *self) {
Base *base_ivars = Base_IVARS(self);
Parent *parent_ivars = Parent_IVARS(self);
Child *child_ivars = Child_IVARS(self);
MyChild *mychild_ivars = MyChild_IVARS(self);
if (parent_ivars->field = 1 && mychild_ivars->subfield == 2) {
mychild_ivars->result = child_ivars->order;
}
else {
mychild_ivars->result = base_ivars->type[parent_ivars->number];
}
return base_ivars->id;
}
I think this matches what is proposed? If so, even the scrolling back
and forth to get this example right was painful. If it involved
flipping back and forth between 4 different files (3 of which are
unfamiliar) it would be excruciating.
Along that lines, I think I left at least one error in "New" -- how
long does it take to spot it?
The "Old" version is easy because one only needs to know the
properties of the object, and in a pinch, you can just look at the
generated C. Or even easier, your editor or IDE can look at it and
provide you with autocompletion for all available struct members. I
use emacs, so I'm sure it's possible to make that work somehow, but I
don't expect it to be easy.
My second "complaint" is that despite this, we still end up with base
classes that are quite fragile. The benefit (and it is significant)
is that we gain the ability to add member variables to the end of the
structs for each parent class. But programmer discipline is needed,
for if they are added elsewhere compiled modules will break even
though the local recompile works just fine. Moving a variable from
Grandparent to Parent causes the same problems. Deletion is always
going to be tricky, but it would be nice to get an error message
rather than a segfault. If we are going down this route, I think we
should aim for truly robust rather than just less fragile.
On the bright side, I don't think that performance is going to be that
big of an issue. Maybe 50 cycles per function for the accessing a
variable once the lookups are cached in L3? Another dozen for the
pipeline to finish adding the offsets? Repeated access should be much
faster, and we can easily cache a local pointer for tight loops.
Taking a blind stab, maybe 25% initially which we can reduce to 10% by
hitting a few hotspots? Making it fast again while gaining the
flexibility seems like a fun challenge.
3. Alternative Proposal
If we want greater clarity and robustness, and assuming I'm not
missing something obvious about Nick's proposal, I think we'll need to
work at the level of the individual variables rather than having a
per-class offset. If we're willing to tolerate having lots of new
symbols (and I don't see that we shouldn't) I think this can be quite
straightforward, both for syntax and implementation. We can sort out
the performance later once we say what sort of hit it actually is.
I'd propose something like this:
NateNew:
// generated by cfish but no typedef
struct __Child {
int id; // Base
int *type; // Base
int field; // Parent
int order; // Parent
int number; // Child
int subtype; // Child
}
// public but opaque typedef to boobytrap direct usage
typedef struct {
void[sizeof(struct __Child)] *direct_access_not_allowed;
} Child_t;
// symbols in shared object set to values at library compile time
int __Child_id = offsetof(struct __Child, id);
int * __Child_type = offsetof(struct __Child, type);
int __Child_field = offsetof(struct __Child, field);
int __Child_order = offsetof(struct __Child, order);
int __Child_number = offsetof(struct __Child, number);
int __Child_subtype = offsetof(struct __Child, subtype);
// approximate macro in public API, likely not working nor free of pitfalls
#define Child(self, var) ( \\
(typeof( ((struct __Child *)0)->var)) \\
((char *) self + __Child_ ## var) \\
)
// macro must have correct type, check that var exists, and work as an lvalue
// generated by cfish for user class but no typedef
struct __MyChild {
int id; // Base
int *type; // Base
int field; // Parent
int order; // Parent
int number; // Child
int subtype; // Child
int result; // MyChild
int subfield; // MyChild
}
// opaque typedef generated by cfish for allocation and typechecking
typedef struct {
void[sizeof(struct __MyChild)] *direct_access_not_allowed;
} MyChild;
int MyChild_prepare_result(MyChild *self) {
if (MyChild(self, field) == 1 && MyChild(self, subfield) == 2) {
MyChild(self, result) = MyChild(self, order);
}
else {
MyChild(self, result) = self->type[self->number];
}
return self->id;
}
I'm sure it's full of egregious holes that need to be patched, but I
like that it's a search-and-replace away from struct notation, doesn't
require knowledge of the object hierarchy, reports runtime errors at
startup, and allows for arbitrary reordering of the base classes.
Performance will initially be several notches worse than Nick's
proposal, but in the same ballpark. But if we can ever figure out how
to do a proper Link Time Optimization of the lookups, they both have
about the same potential.
There are probably other ways to accomplish this, but the key is that we need
1) a fleshed out struct to use for member type, existence, and autocompletion
2) an opaque struct used for object-level type checking and allocation size
3) a macro to access the real offsets that are loaded from the shared object
4) a way to prevent the object from being accessed by any other means
5) a readable syntax that can be used on the left or right of an assignment
I think this is achievable.
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Fri, Sep 21, 2012 at 11:30 PM, Nathan Kurz <na...@verse.com> wrote:
> On Tue, Sep 18, 2012 at 11:16 AM, Marvin Humphrey
>> The proposal on the table isn't any more complicated than a struct. The way
>> the fields are laid out in memory is identical.
>
> While the second sentence is true, I strongly disagree with the first.
> The cognitive load is extreme.
I don't think that Nick's proposal is hard to understand. Member variables
are still accessed via a struct; the interface change is that you have to look
up that struct first.
Before:
Foo*
Foo_init(Foo *self, int i, float f) {
self->i = i;
self->f = f;
return self;
}
After:
Foo*
Foo_init(Foo *self, int i, float f) {
Foo_IVARS *ivars = Foo_GET_IVARS(self);
ivars->i = i;
ivars->f = f;
return self;
}
In my view, the biggest downside is that the extra code to look up the struct
is irritatingly verbose. It's analogous to `my $self = shift;` -- not hard to
grok, just tiresome to write over and over.
> I worry we'd just be recreating C++ badly here. What are you reasons for
> not just making the jump at this point?
As argued upthread:
I think it's an outmoded approach in the era of CPAN, rubygems, etc. The
fragile coupling of C++ is poorly suited for distributed development and
dynamic linking.
I also happen to agree with classic critiques of C++ as baroque and
overwrought, but my main objection to to C++ is that it is difficult to
integrate with dynamic language ecosystems -- and the fragile base class
problem is a big part of that.
With that as background... does it make sense now why I'm so vehemently
opposed to saddling Clownfish with what I see as one of the most problematic
flaws of C++?
> The part I'd prefer not to give up is the ability to reason about the
> efficiency of a routine by eyeing the source.
I understand this concern, but it seems to me that the lookup routine is quite
transparent -- to a fault, arguably. We're certainly not hiding the fact that
the extra lookup is happening.
> While I appreciate the intent, and think I understand the "Fragile Base
> Problem" pretty well, I don't think it's pressing issue to allow member
> variables to be added ad libitum to the core classes.
We're at an impasse, then. I'm fundamentally opposed to publishing a
Clownfish C API where all instance variables are exposed as struct members.
Marvin Humphrey
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
On Tue, Sep 18, 2012 at 11:16 AM, Marvin Humphrey
> These OFFSET variable lookups are merely a question of optimization. We
> haven't even done significant benchmarking to measure how much they cost --
> the only data point we have is that when I marked all methods in InStream and
> OutStream as `final` (so that those method symbols resolve as direct function
> invocations rather than go through vtable dispatch) there wasn't a measurable
> change on our indexing benchmark.
A good hope, but I think/hope there are going to be many more variable
accesses than function calls. But I suppose one can always cache the
offset locally in the very few few ultra-critical loops.
>> I love the simplicity of a simple struct: no macros, no accessors, no
>> opacity.
>
> I can't get on board with "no opacity" being a good thing. :\
I think I agree with you, and am using "opacity" in a difference sense
here. Data hiding for non-API items is great. But I'm referring to
the "what you see is what you get" aspect of C that makes me prefer it
to C++.
When one calls uses a struct in C, one knows that nothing untoward is
going on behind the scenes. Making every access to something that
feels like a struct do a couple lookups and extra memory accesses
strikes me as untoward. For the base library, I _want_ portable
assembly, and _want_ to be able to accurately guess what's happening
behind the scenes.
> Expecting programmers to reserve slots with dummy variables is a grotesque
> workaround and a huge burden.
We'll, very rarely would any users of the Lucy library need to do
this. It would be only be for the parts of the core library that we
feel compelled to make part of the published API but that for some
reason can't be finalized.
> It might be the only way to make C++ work, but
> can't we learn from the past rather than repeat it?
Well, I suppose BeOS is not a great example to be looking at as a
model of success. :)
>> If there is any way we can keep it [simple struct access] for instance
>> variables, I think we should.
>
> The proposal on the table isn't any more complicated than a struct. The way
> the fields are laid out in memory is identical.
While the second sentence is true, I strongly disagree with the first.
The cognitive load is extreme.
In addition to wanting it to act like C, I think we benefit from
making it look like C. I'm also afraid that we're going so far into a
private dialect that we won't be accessible to C programmers who want
to jump in. We've already got the barrier of the Clownfish hierarchy.
While I suppose you can argue that anyone who makes it over that
hurdle won't be turned off by this, we need to be accessible to
host-language experts who haven't used a lot of C.
> The only difference is that unlike Java and C#, C only provides native syntax
> for accessing a member variable when its offset is known at compile-time.
> Some parts of C are antiquated. This is one.
I worry we'd just be recreating C++ badly here. What are you reasons
for not just making the jump at this point?
The part I'd prefer not to give up is the ability to reason about the
efficiency of a routine by eyeing the source.
> Furthermore, the quasi-accessor does the thing by default, while direct
> access, which is meant to be simple, ironically requires that users possess a
> sophisticated understanding of the "fragile base class" problem in order to
> program safely.
What I like about the "simple struct" approach, is that the demands
are solely on the authors of the core Lucy library. No need to always
use an inexplicable macro. The extension writers and language porters
never have to worry about it: they use a struct, and it just works.
I think the only time there would be any danger to users would be if
we were to accidentally make a release that altered the layout of the
core structs. I don't see this as being a large danger. While I
appreciate the intent, and think I understand the "Fragile Base
Problem" pretty well, I don't think it's pressing issue to allow
member variables to be added ad libitum to the core classes.
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Mon, Sep 17, 2012 at 8:49 PM, Nathan Kurz <na...@verse.com> wrote:
> On Mon, Sep 17, 2012 at 3:31 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
>> On Mon, Sep 17, 2012 at 1:24 PM, Nathan Kurz <na...@verse.com> wrote:
>>> http://blog.omega-prime.co.uk/?p=121
>>
>> Rats. I wish what was described in that post actually worked. It would be
>> so nice if we could alias e.g. `lucy_Query_to_string_OFFSET` to
>> `cfish_Obj_to_string_OFFSET`.
>>
>> Even better if we could alias to a constant, so that e.g.
>> `lucy_Query_to_string_OFFSET` could be replaced by `72` at link-time.
>
> I'm hoping there still is a way, and hoping that way isn't too awful.
> I mean, it's obviously possible, just a question of how low we have to
> go. Do you suppose it would be awkward to distribute our own
> dynamic linker? :)
Heh. You could say that's how Java and C# solve problems like this, if you
think of JIT compilers as linkers on steroids. :)
In keeping with the metaphor of a clownfish forming a symbiotic relationship
with its host anemone, we're trying to work with the existing system for
linking. So far we're doing pretty well.
These OFFSET variable lookups are merely a question of optimization. We
haven't even done significant benchmarking to measure how much they cost --
the only data point we have is that when I marked all methods in InStream and
OutStream as `final` (so that those method symbols resolve as direct function
invocations rather than go through vtable dispatch) there wasn't a measurable
change on our indexing benchmark.
Weak symbols seem tantalizing but I'm not sure they can help:
http://en.wikipedia.org/wiki/Weak_symbol
The Lucy DSO could define `cfish_Obj_to_string_OFFSET` as a weak symbol, which
would be overridden by the version supplied by the Clownfish DSO. But even
then, each access would still be a variable lookup, and would involve an extra
level of indirection via the GOT[1] to boot. Nick's approach of having each
DSO maintain its own OFFSET variables with `hidden` visibility (which also
allows us to reduce the _number_ of OFFSET variables) seems better.
FWIW, here's somebody else trying to do the same thing we are:
http://stackoverflow.com/questions/9753723/c-constants-defined-at-link-time
> The 'ioctl' wouldn't be a 'perform' function, but a link to a
> substruct. If the padding ran out and we desperately needed to add
> another variable to a parent class, we'd add a pointer to a struct in
> the last space. Then one would reference foo->extra->new1,
> foo->extra->new2. This would hold us until the next major release,
> when we'd clean up, fold this into the main struct, and add extra
> padding if still needed. Not too pretty, but a decent backstop. And
> if we plan ahead as to where additions are most likely, we shouldn't
> ever have to resort to it.
>
> I love the simplicity of a simple struct: no macros, no accessors, no
> opacity.
I can't get on board with "no opacity" being a good thing. :\
Keeping struct definitions opaque is fundamental information hiding. It's
problematic if either users or compilers "know" the offsets at which member
variables may be accessed. If users "know" offsets, some fraction of them
are going to manipulate member variables directly, piercing encapsulation.
If compilers "know" offsets, we get fragile base class problems because of
incorrect compile-time assumptions that those offsets are constant forever.
Expecting programmers to reserve slots with dummy variables is a grotesque
workaround and a huge burden. It might be the only way to make C++ work, but
can't we learn from the past rather than repeat it?
> If there is any way we can keep it for instance variables, I
> think we should.
The proposal on the table isn't any more complicated than a struct. The way
the fields are laid out in memory is identical.
The only difference is that unlike Java and C#, C only provides native syntax
for accessing a member variable when its offset is known at compile-time.
Some parts of C are antiquated. This is one.
For the user, accessing a member vars struct via an inline function like
`Foo_Get_IVARS()` is no more onerous than accessing a nested struct:
void
Foo_get_num(Foo *self) {
return Foo_GET_IVARS(self)->num;
}
void
Foo_get_num(Foo *self) {
return self->foo_extra->num;
}
Furthermore, the quasi-accessor does the thing by default, while direct
access, which is meant to be simple, ironically requires that users possess a
sophisticated understanding of the "fragile base class" problem in order to
program safely.
Marvin Humphrey
[1] GOT: Global Offset Table
http://en.wikipedia.org/wiki/Position-independent_code#Technical_details
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
On Mon, Sep 17, 2012 at 3:31 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
> On Mon, Sep 17, 2012 at 1:24 PM, Nathan Kurz <na...@verse.com> wrote:
>> http://blog.omega-prime.co.uk/?p=121
>
> Rats. I wish what was described in that post actually worked. It would be
> so nice if we could alias e.g. `lucy_Query_to_string_OFFSET` to
> `cfish_Obj_to_string_OFFSET`.
>
> Even better if we could alias to a constant, so that e.g.
> `lucy_Query_to_string_OFFSET` could be replaced by `72` at link-time.
I'm hoping there still is a way, and hoping that way isn't too awful.
I mean, it's obviously possible, just a question of how low we have to
go. Do you suppose it would be awkward to distribute our own dynamic
linker? :)
>
>> I think the general approach of this paper: http://2f.ru/holy-wars/fbc.html
>> Old, and C++, but a nice simple approach. Add padding where you think
>> you'll need it, and have an "ioctl" type safety net. We may also be
>> able to use their trick of padding both the top and bottom of the
>> VTable to allow us to move things between parent and child.
>
> Yeah, some people abide by such constraints:
>
> http://techbase.kde.org/Policies/Binary_Compatibility_Issues_With_C%2B%2B
>
> I think it's an outmoded approach in the era of CPAN, rubygems, etc. The
> fragile coupling of C++ is poorly suited for distributed development and dynamic
> linking. Personally, I'm not willing to put up with it.
>
> Clownfish solves most of these issues already -- we don't have to pull any
> silly tricks to preserve vtable ABI compat, for example. Only member variable
> issues remain and stand in the way of a comprehensive solution to the fragile
> base class problem.
Yes, I essentially agree. I was probably unclear, and wasn't
suggesting this was a good solution for VTables. It's not. Instead,
I was suggesting that we might take an analogous approach for instance
variables. I think the main weakness of the BeOS approach is how it
handles overrides. Is it even possible to override an instance
variable? Instead, it's more frequently a matter of additions, and
occasionally movement of a variable between a parent and a child. As
such, I think we could do quite well sticking with simple structs and
padding them with some extra internal space.
The 'ioctl' wouldn't be a 'perform' function, but a link to a
substruct. If the padding ran out and we desperately needed to add
another variable to a parent class, we'd add a pointer to a struct in
the last space. Then one would reference foo->extra->new1,
foo->extra->new2. This would hold us until the next major release,
when we'd clean up, fold this into the main struct, and add extra
padding if still needed. Not too pretty, but a decent backstop. And
if we plan ahead as to where additions are most likely, we shouldn't
ever have to resort to it.
I love the simplicity of a simple struct: no macros, no accessors, no
opacity. If there is any way we can keep it for instance variables, I
think we should.
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Mon, Sep 17, 2012 at 1:24 PM, Nathan Kurz <na...@verse.com> wrote:
> http://blog.omega-prime.co.uk/?p=121
Rats. I wish what was described in that post actually worked. It would be
so nice if we could alias e.g. `lucy_Query_to_string_OFFSET` to
`cfish_Obj_to_string_OFFSET`.
Even better if we could alias to a constant, so that e.g.
`lucy_Query_to_string_OFFSET` could be replaced by `72` at link-time.
> I think the general approach of this paper: http://2f.ru/holy-wars/fbc.html
> Old, and C++, but a nice simple approach. Add padding where you think
> you'll need it, and have an "ioctl" type safety net. We may also be
> able to use their trick of padding both the top and bottom of the
> VTable to allow us to move things between parent and child.
Yeah, some people abide by such constraints:
http://techbase.kde.org/Policies/Binary_Compatibility_Issues_With_C%2B%2B
I think it's an outmoded approach in the era of CPAN, rubygems, etc. The
fragile coupling of C++ is poorly suited for distributed development and dynamic
linking. Personally, I'm not willing to put up with it.
Clownfish solves most of these issues already -- we don't have to pull any
silly tricks to preserve vtable ABI compat, for example. Only member variable
issues remain and stand in the way of a comprehensive solution to the fragile
base class problem.
Marvin Humphrey
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
On Mon, Sep 17, 2012 at 9:57 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> On 17/09/2012 11:55, Nathan Kurz wrote:
>> VTables disappear. Unfortunately, this is the less fleshed out part
>> of my plan. I'm serious, though.
>> ...
>
> I wonder how you want to make virtual method dispatch work with this kind of
> scheme.
I'm terrible on terminology, and even worse when it comes to mapping
these to Clownfish. Am I right that all of our object methods are
'virtual' now, so this you're wondering about how method inheritance
works at all? Unfortunately, this core essential feature is part of
what I referred to as "not yet fleshed out".
The silly straightforward way would be to just chain the functions.
New_foo() is stubbed to call Parent_foo(), which in turn may choose to
call Grandparent_foo(). Sounds slow, but it's possible that Link TIme
Optimization might substitute be able to re-optimize it.
The trickier way would be to do it with symbol aliasing. Define
New_foo() as an alias for Parent_foo(), and let the runtime linker
handle it behind the scenes like any other shared symbol. But while
this works on paper, I don't know how it fares in practice:
http://blog.omega-prime.co.uk/?p=121
Or am I many steps behind you and I'm missing the elephant?
---
Part of my interest in this direction is that it doesn't affect how we
handle the instance variables. Keeping them. By keeping that
independent (and ideally just a simple struct) we keep the complexity
down.
Another point is that I don't think we have to move in this direction
in any hurry. I think adding some padding to futureproof our current
VTables with hold us through a major release cycle if needed.
I think the general approach of this paper: http://2f.ru/holy-wars/fbc.html
Old, and C++, but a nice simple approach. Add padding where you think
you'll need it, and have an "ioctl" type safety net. We may also be
able to use their trick of padding both the top and bottom of the
VTable to allow us to move things between parent and child.
This is definitely a blue sky approach, but I think it's a
particularly dangerous one.
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nick Wellnhofer <we...@aevum.de>.
On 17/09/2012 11:55, Nathan Kurz wrote:
> On Mon, Sep 17, 2012 at 1:49 AM, Nathan Kurz <na...@verse.com> wrote:
>> I've been reading along, and will try to put my thoughts into typed
>> words soon.
>
> Preliminary questions followed by preliminary thoughts:
>
> What are the bounds of the problem that we are trying to solve here?
> Is it fair to summarize it to "we want to be able to add methods and
> instance variables to base classes without breaking shared libraries
> that inherit from them? Specifically is it OK to do only this and
> not worry about breakage that can be easily avoided, like reordering
> the VTable, and hard to solve stuff like having an intermediate class
> override something new in its parent?
IMO, we should try to support all of this if it doesn't come at too high
a cost.
> How much pressure is there to reduce the memory footprint of these
> objects? Are there cases where we are allocating millions of them at
> a time? Related to this, are we trying to improve Clownfish in
> general, or only as is required for Lucy? I'd guess that while we
> should be memory conscious, adding a few bytes per layer of
> inheritance wouldn't be a problem for our specific uses.
I think the idea is really to improve Clownfish in general, and break it
out as a stand-alone product. If we separate the Clownfish core classes
from Lucy, we'll already be faced with all the binary compatibility issues.
In the long run, Lucy should also benefit from making the Clownfish
object system more modular, especially wrt compiled extensions.
> VTables disappear. Unfortunately, this is the less fleshed out part
> of my plan. I'm serious, though.
>
> I think we can make the linker do a lot of our work that we currently
> do ourselves. The VTables would be dispersed into the symbol tables,
> identified only by naming convention. If you create a class Foo
> inheriting from Parent, "Foo_function" starts as a symbolic alias for
> "Parent_function". If you want to override it, you give it a real
> definition. The collection of symbols within "Foo_*" plus some form
> of Super is all you've got.
I wonder how you want to make virtual method dispatch work with this
kind of scheme.
Nick
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Mon, Sep 17, 2012 at 8:23 AM, Kurt Starsinic <ks...@gmail.com> wrote:
> I'm curious as to what the instant problem is. I'm familiar with
> fragile base class becoming an issue in a few cases:
>
> 1) We're handing out headers + precompiled libraries to end users.
> They're going to build subclasses, and later they might re-link their
> applications with newer versions of the libraries, having skipped
> re-compilation in error. Boom.
> Which of these (or which other scenarios) are we running into?
The first case is the one we're concerned about.
It is possible to write pure Perl subclasses of Lucy classes, and this works
well for things like QueryParser which are not performance bottlenecks.
However it doesn't work so well for classes like Matchers which have methods
which are invoked once per matching document during a search. The method call
overhead is too high and so the subclasses do not scale well to large
collections.
The solution, we believe, is to publish a C API which allows users to create
compiled subclasses. Right now in our (prototype) API, superclass struct
definitions are exposed and subclasses must use them to compose their own
struct definitions. This makes these compiled subclasses vulnerable to
"fragile base class" problems should a superclass be recompiled with added,
removed, or reordered member variables.
The problem is particularly pernicious because of what it means to "re-link" a
Perl application. If the user upgrades Lucy using the CPAN apparatus, the
packaging system does not know that it needs to force re-compilation and
re-installation for downstream modules which depend on Lucy's ABI.
The "re-link" stage happens dynamically, at run-time:
use Lucy;
use LucyX::Analysis::WhitespaceTokenizer;
If the composition of the member variables in any of WhitespaceTokenizer's
superclasses has changed, the app will likely segfault as soon as a
WhitespaceTokenizer is created or used.
That's not acceptable, and that's why it's important to solve the issue now
before we publish an API which exposes our users to a fragile base class
problem.
Marvin Humphrey
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Kurt Starsinic <ks...@gmail.com>.
I'm curious as to what the instant problem is. I'm familiar with
fragile base class becoming an issue in a few cases:
1) We're handing out headers + precompiled libraries to end users.
They're going to build subclasses, and later they might re-link their
applications with newer versions of the libraries, having skipped
re-compilation in error. Boom.
2) The codebase is huge, and under frequent extreme refactoring.
Re-compiling big pieces of the application after making a small
modification to a widely-used base class is prohibitiively expensive.
Yuk.
3) The codebase's build dependencies aren't correctly stated. When
changing a base class and doing a rebuild (without forcing a clean
rebuild), you end up with a surreptitiously broken application. *Sad
trombone*
Which of these (or which other scenarios) are we running into?
- Kurt
On Mon, Sep 17, 2012 at 5:55 AM, Nathan Kurz <na...@verse.com> wrote:
> On Mon, Sep 17, 2012 at 1:49 AM, Nathan Kurz <na...@verse.com> wrote:
>> I've been reading along, and will try to put my thoughts into typed
>> words soon.
>
> Preliminary questions followed by preliminary thoughts:
>
> What are the bounds of the problem that we are trying to solve here?
> Is it fair to summarize it to "we want to be able to add methods and
> instance variables to base classes without breaking shared libraries
> that inherit from them? Specifically is it OK to do only this and
> not worry about breakage that can be easily avoided, like reordering
> the VTable, and hard to solve stuff like having an intermediate class
> override something new in its parent?
>
> How much pressure is there to reduce the memory footprint of these
> objects? Are there cases where we are allocating millions of them at
> a time? Related to this, are we trying to improve Clownfish in
> general, or only as is required for Lucy? I'd guess that while we
> should be memory conscious, adding a few bytes per layer of
> inheritance wouldn't be a problem for our specific uses.
>
> Are we OK with requiring module developers to know the precise
> ancestry of their objects by keeping track of which parent added which
> variables? I think a lot of the examples require this, but I might
> be misreading them. If true, this seems like it adds another
> significant barrier to new contributors.
>
> Here'a rough vision of my poorly fleshed out goal having even more
> transparency than we do now:
>
> Each object is just a simple struct. Access is via "foo->name". We
> do this by padding the parent structs with a couple extra slots in
> case we need them. If they fill up and we still need more, we can
> punt to a lookup table as the last entry.
>
> We break the Lucy ABI at ever major version and adjust padding as
> needed. If a class is feeling solid and final, we can remove the
> padding. If still fluid, we add more. I don't think inability to
> move a variable from parent to grandparent will really be a problem.
>
> VTables disappear. Unfortunately, this is the less fleshed out part
> of my plan. I'm serious, though.
>
> I think we can make the linker do a lot of our work that we currently
> do ourselves. The VTables would be dispersed into the symbol tables,
> identified only by naming convention. If you create a class Foo
> inheriting from Parent, "Foo_function" starts as a symbolic alias for
> "Parent_function". If you want to override it, you give it a real
> definition. The collection of symbols within "Foo_*" plus some form
> of Super is all you've got.
>
> Adding methods becomes non-dangerous. Rearranging isn't a problem,
> because no set order exists. Deleting either creates a clear link
> time error or everything runs fine. Even moving methods between
> parent and grandparent doesn't fluster us. I think it's all
> solvable. My fears are mostly speed, related to the multiple layers
> of indirect lookups referred to in the previous message.
>
> The philosophy I'd like to keep is that we do can lots of complex
> things within Clownfish, but the finished output is simple C code, and
> the finished libraries are standard libraries that could have been
> produced without actually using Clownfish. Instead of creating a new
> language, we're just generating a standardized binary using some
> custom made tools that make the job easier.
>
> --nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
On Mon, Sep 17, 2012 at 1:49 AM, Nathan Kurz <na...@verse.com> wrote:
> I've been reading along, and will try to put my thoughts into typed
> words soon.
Preliminary questions followed by preliminary thoughts:
What are the bounds of the problem that we are trying to solve here?
Is it fair to summarize it to "we want to be able to add methods and
instance variables to base classes without breaking shared libraries
that inherit from them? Specifically is it OK to do only this and
not worry about breakage that can be easily avoided, like reordering
the VTable, and hard to solve stuff like having an intermediate class
override something new in its parent?
How much pressure is there to reduce the memory footprint of these
objects? Are there cases where we are allocating millions of them at
a time? Related to this, are we trying to improve Clownfish in
general, or only as is required for Lucy? I'd guess that while we
should be memory conscious, adding a few bytes per layer of
inheritance wouldn't be a problem for our specific uses.
Are we OK with requiring module developers to know the precise
ancestry of their objects by keeping track of which parent added which
variables? I think a lot of the examples require this, but I might
be misreading them. If true, this seems like it adds another
significant barrier to new contributors.
Here'a rough vision of my poorly fleshed out goal having even more
transparency than we do now:
Each object is just a simple struct. Access is via "foo->name". We
do this by padding the parent structs with a couple extra slots in
case we need them. If they fill up and we still need more, we can
punt to a lookup table as the last entry.
We break the Lucy ABI at ever major version and adjust padding as
needed. If a class is feeling solid and final, we can remove the
padding. If still fluid, we add more. I don't think inability to
move a variable from parent to grandparent will really be a problem.
VTables disappear. Unfortunately, this is the less fleshed out part
of my plan. I'm serious, though.
I think we can make the linker do a lot of our work that we currently
do ourselves. The VTables would be dispersed into the symbol tables,
identified only by naming convention. If you create a class Foo
inheriting from Parent, "Foo_function" starts as a symbolic alias for
"Parent_function". If you want to override it, you give it a real
definition. The collection of symbols within "Foo_*" plus some form
of Super is all you've got.
Adding methods becomes non-dangerous. Rearranging isn't a problem,
because no set order exists. Deleting either creates a clear link
time error or everything runs fine. Even moving methods between
parent and grandparent doesn't fluster us. I think it's all
solvable. My fears are mostly speed, related to the multiple layers
of indirect lookups referred to in the previous message.
The philosophy I'd like to keep is that we do can lots of complex
things within Clownfish, but the finished output is simple C code, and
the finished libraries are standard libraries that could have been
produced without actually using Clownfish. Instead of creating a new
language, we're just generating a standardized binary using some
custom made tools that make the job easier.
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nathan Kurz <na...@verse.com>.
On Sun, Sep 16, 2012 at 8:02 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
> What really sticks in my craw is that
> it's the _ELF_ rules which force it to be looked up every last access, but
> it's entirely possible that the lookup won't matter in practice.
I've been reading along, and will try to put my thoughts into typed
words soon. Until then, I'll just stick to this sentence.
I take it you are referring to the requirement of "symbol preemption",
whereby even with a module every symbol must be accessed indirectly in
case some earlier library decided to override it? I don't think this
is actually an ELF rule, but even if so, I think there are ways around
this.
Here's some background on the problem and suggested solutions:
http://software.intel.com/en-us/articles/software-convention-models-using-elf-visibility-attributes/
http://www.macieira.org/blog/2012/01/sorry-state-of-dynamic-libraries-on-linux/
http://www.airs.com/blog/archives/307
The recommended approach is to use ELF symbol visibility attributes to
prevent preemption and allow for optimization within the module.
Since our core is one big shared object, this means that everything in
core can be direct access, although runtime linked user code will
still need indirection.
There are some complicated options discussed in the linked articles,
but for us, I think we can probably just declare all the offsets as
"protected" and be 95% of the way there. If anyone ever does try to
override them, the sky will (silently) fall, but everything else
should just work: core at full speed, user compiled shared libraries
work as you describe, which in most cases is still really fast.
There are a couple other approaches that might be relevant as well,
but perhaps they turned out to be dead ends "-B direct" and "prelink".
I unsure about their current status, and not sure if they offer us
much more than the symbol visibility does. My instinct is that they
don't, but I don't understand them well.
Or are you saying that all shared library globals are implicitly
'volatile' in some way? I don't think there are any preclusions
against caching shared library globals in registers. Are there?
--nate
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Marvin Humphrey <ma...@rectangular.com>.
Hi, Nick,
Kudos for thinking outside the box!
On Sun, Sep 16, 2012 at 7:45 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> This leaves the problem of converting the members struct pointers from a
> source class to a target class for every method call. The obvious approach
> is to somehow work back to the start of the memory region of the object, and
> then apply an offset appropriate for the target class. Finding the the start
> of the object could be done by adding a field to every members struct. This
> would mean two additional fields if you want to keep direct vtable access
> (e.g. for method calls) from member structs. All of that looks rather
> expensive to me.
In addition to being expensive, it seems to me that it would also be complex and
error prone. The proposal I made back in May, inspired by C++, was also
pretty labyrinthine, but if it had worked the way I'd hoped, the complexity
would have been hidden within the method dispatch apparatus -- from the
standpoint of the programmer, `self` would have always Just Worked.
I'm concerned about making programmers think about any invocant more
complicated than `self` on its own. Getting at the `members` struct is also
kind of a pain, but at least it's an easily-understood, logical step and hard
to mess up.
> So in terms of what arguments a method could receive for the 'self' object,
> I can see the following solutions (in my order of preference):
>
> 1. Foo_set_num(Foo *self, int num)
>
> Cons:
> * One additional line of code per method for members lookup
> * One additional global variable access per method call for
> members lookup
I concur with you that this is our best option. I think it's the most sound
and straightforward construct/algorithm available to us.
It's frustrating that we have those global variable accesses for e.g.
`Foo_IVARS_OFFSET`, but at least it's possible to set that variable at
VTable-init time and forget about it. What really sticks in my craw is that
it's the _ELF_ rules which force it to be looked up every last access, but
it's entirely possible that the lookup won't matter in practice. We can
benchmark the result of setting all the IVARS_OFFSET variables to compile-time
constants if we want to find out how much we're paying.
For the record, I thought a little harder today about aliasing and concluded
that there's no way to turn off -fno-strict-aliasing even if `self` is allowed
to point at different places within an object. Even if `A` does not point at
the exact same address as `B`, what matters is that it can still be alias for
_the same object_ -- so you have to be pessimistic about caching field values
in registers unless your compiler can do serious aliasing analysis and suss
out which variables can alias and which can't.
Another note: making the transition to members structs will be
straightforward, if a little tedious.
1. #define `Foo_IVARS` as `Foo`
2. Set Foo_GET_IVARS() to return `self`.
3. Change over all struct access in the Lucy core to use IVARS.
4. Change over Foo_IVARS to be only class-specific member variables.
5. Stop providing struct defs for `Foo`.
Marvin Humphrey
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nick Wellnhofer <we...@aevum.de>.
On 16/09/2012 15:17, Nick Wellnhofer wrote:
> Another solution is to provide the members pointer as an argument to
> every method:
>
> void
> Foo_set_num(Foo *self, Foo_MEMBERS *members, int num) {
> members->num = num;
> }
>
> The offset would then be applied in the method wrappers (Foo_Set_Num
> without the members argument). The same technique as in Marvin's initial
> approach could be used to store method and members offsets at a single
> memory location. This would give a slight performance benefit (mainly on
> x86, 32 bits) by avoiding a global variable lookup.
>
> But I'm not convinced it's worth the added complexity. I still prefer to
> make the lookup of the members struct explicit.
Thinking more about it, it's also possible to pass only member structs
to methods if you add a pointer back to 'self' to every struct. Or you
could use a pointer directly to the VTable. This is exactly what
Marvin's initial approach does.
This leaves the problem of converting the members struct pointers from a
source class to a target class for every method call. The obvious
approach is to somehow work back to the start of the memory region of
the object, and then apply an offset appropriate for the target class.
Finding the the start of the object could be done by adding a field to
every members struct. This would mean two additional fields if you want
to keep direct vtable access (e.g. for method calls) from member
structs. All of that looks rather expensive to me.
So in terms of what arguments a method could receive for the 'self'
object, I can see the following solutions (in my order of preference):
1. Foo_set_num(Foo *self, int num)
Cons:
* One additional line of code per method for members lookup
* One additional global variable access per method call for
members lookup
2. Foo_set_num(Foo *self, Foo_MEMBERS *members, int num)
Pros:
* Lookup of members can probably be optimized slightly
(at the expense of some VTable memory)
Cons:
* Additional method argument
3. Foo_set_num(Foo_MEMBERS *self, int num)
Cons:
* Memory overhead per members struct
* Conversion of 'members' to another class for method
calls is probably too expensive
Nick
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nick Wellnhofer <we...@aevum.de>.
On 09/09/2012 21:05, Marvin Humphrey wrote:
> On Sun, Sep 9, 2012 at 4:00 AM, Nick Wellnhofer <we...@aevum.de> wrote:
>> void
>> Sub_method(void *self) {
>> Sub_MEMBERS *members = Sub_get_members(self);
>> members->sub_num = 1;
>> members->sub_float = 1.0;
>>
>> // Only safe if Base is in the same parcel
>> Base_MEMBERS *base_members = Base_get_members(self);
>> base_members->base_num = 1;
>> base_members->base_float = 1.0;
>> }
>
> I'd originally thought to avoid this approach because of the extra line of
> code, but perhaps it's not so bad after all. Plus, there's an idiom for
> single line access;
>
> void
> Foo_set_num(Foo *self, int num) {
> Foo_MEMBERS(self)->num = num;
> }
Another solution is to provide the members pointer as an argument to
every method:
void
Foo_set_num(Foo *self, Foo_MEMBERS *members, int num) {
members->num = num;
}
The offset would then be applied in the method wrappers (Foo_Set_Num
without the members argument). The same technique as in Marvin's initial
approach could be used to store method and members offsets at a single
memory location. This would give a slight performance benefit (mainly on
x86, 32 bits) by avoiding a global variable lookup.
But I'm not convinced it's worth the added complexity. I still prefer to
make the lookup of the members struct explicit.
Nick
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Sun, Sep 9, 2012 at 4:00 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> I've also been thinking about the fragile base class problem, and as food
> for thought I'd like to present what I consider the easiest solution.
Your general approach works for me, Nick.
> Note that my approach doesn't work with cross-parcel access of member
> variables, not even with accessing member vars of superclasses if the
> superclass comes from another parcel. But I think that's something we could
> live with.
That's a feature! :)
> Accessing the member vars of other classes is bad for encapsulation anyway.
Exactly. Right now, Clownfish only offers one option for member variable
access control: all members have `protected` exposure. Unfortunately,
allowing direct access to member variables with `protected` exposure causes
the same kinds of problems as allowing direct access by making a variable
`public`.
After this change, all member variables will be private by default, though
within a given parcel, you will have the option of enabling direct access
file-by-file.
> With this restriction, you only have to care about the total size of the
> member vars of a super class, not about the actual layout.
For what it's worth, we could define the macros I suggested in terms of yours.
#define Foo_num(self) \
(*((int*)SI_member_address(self, \
Foo_MEMBERS_OFFSET + offsetof(Foo, num))))
Since offsetof() evaluates to a compile-time constant, the additional math
would incur negligible runtime performance impact -- but we get to use one
OFFSET var per class rather than one per member variable.
> void
> Sub_method(void *self) {
> Sub_MEMBERS *members = Sub_get_members(self);
> members->sub_num = 1;
> members->sub_float = 1.0;
>
> // Only safe if Base is in the same parcel
> Base_MEMBERS *base_members = Base_get_members(self);
> base_members->base_num = 1;
> base_members->base_float = 1.0;
> }
I'd originally thought to avoid this approach because of the extra line of
code, but perhaps it's not so bad after all. Plus, there's an idiom for
single line access;
void
Foo_set_num(Foo *self, int num) {
Foo_MEMBERS(self)->num = num;
}
Bikeshedding questions: MEMBERS, or IVARS? Or both? Or something else?
`IVARS` -- an abbreviation of "instance variables" saves two letters. (Also
FWIW, in Java and C++ both "class variables" and "instance variables" are
"member variables" -- so "members" is a superset.)
void
Sub_method(void *self) {
Sub_IVARS *ivars = Sub_MEMBERS(self);
ivars->sub_num = 1;
ivars->sub_float = 1.0;
// Only safe if Base is in the same parcel
Base_IVARS *base_ivars = Base_MEMBERS(self);
base_ivars->base_num = 1;
base_ivars->base_float = 1.0;
}
`Sub_get_members` bothers me because it doesn't use the all caps convention
which we've informally reserved and therefore looks like userland code.
(`Foo_num` bothers me for the same reason.) Also the underscore in the type
name "Sub_MEMBERS" bothers me, but I guess SubMEMBERS isn't a good
alternative.
> The biggest drawback I can see is that objects become void pointers, and
> we'll lose some of the type-checking that the C compiler currently performs
> for us. But that's something other solutions to the fragile base class
> problem will also have to deal with.
Is using void pointers really mandatory? I'm not seeing it.
I think we can continue to use struct types for classes. We still get the
type checking benefits even if we never define the struct layout and leave the
type opaque.
void
Sub_method(Sub *self) {
Sub_MEMBERS *members = Sub_get_members(self);
members->sub_num = 1;
members->sub_float = 1.0;
// Only safe if Base is in the same parcel
Base_MEMBERS *base_members = Base_get_members((Base*)self);
base_members->base_num = 1;
base_members->base_float = 1.0;
}
In my view, that type checking is very important -- it's too easy to make
mistakes without it which can lead to severe memory errors.
Marvin Humphrey
Re: [lucy-dev] Fragile base class problem, revisited
Posted by Nick Wellnhofer <we...@aevum.de>.
I've also been thinking about the fragile base class problem, and as
food for thought I'd like to present what I consider the easiest
solution. Note that my approach doesn't work with cross-parcel access of
member variables, not even with accessing member vars of superclasses if
the superclass comes from another parcel. But I think that's something
we could live with. Accessing the member vars of other classes is bad
for encapsulation anyway. Using an accessor method will of course be
supported.
With this restriction, you only have to care about the total size of the
member vars of a super class, not about the actual layout. So if we keep
the current way of appending member vars of subclasses, all we have to
know is the total size of the member vars of all superclasses and use
that as offset for the member vars of a subclass.
To implement this, member vars are broken up into structs for every
class, and every class has a global that contains the offset of the
class' member var struct. These offsets can then be computed at run-time
during initialization to adjust for possible changes in the size of
superclasses from other parcels.
Access of member vars would then look something like this (very much
like the code in Marvin's previous mail, only with a single offset per
class):
static inline void*
SI_member_address(void *self, size_t offset) {
return (char*)self + offset;
}
typedef struct Base_MEMBERS {
int base_num;
float base_float;
} Base_MEMBERS;
// Will be 0 for the top-most class in the hierarchy
extern size_t Base_MEMBERS_OFFSET;
static inline Base_MEMBERS*
Base_get_members(void *self) {
return (Base_MEMBERS*)
SI_member_address(self, Base_MEMBERS_OFFSET);
}
typedef struct Sub_MEMBERS {
int sub_num;
float sub_float;
} Sub_MEMBERS;
// Will be (Base_MEMBERS_OFFSET + sizeof(Base_MEMBERS))
extern size_t Sub_MEMBERS_OFFSET;
static inline Sub_MEMBERS*
Sub_get_members(void *self) {
return (Sub_MEMBERS*)
SI_member_address(self, Sub_MEMBERS_OFFSET);
}
void
Sub_method(void *self) {
Sub_MEMBERS *members = Sub_get_members(self);
members->sub_num = 1;
members->sub_float = 1.0;
// Only safe if Base is in the same parcel
Base_MEMBERS *base_members = Base_get_members(self);
base_members->base_num = 1;
base_members->base_float = 1.0;
}
The biggest drawback I can see is that objects become void pointers, and
we'll lose some of the type-checking that the C compiler currently
performs for us. But that's something other solutions to the fragile
base class problem will also have to deal with.
Nick