-
Notifications
You must be signed in to change notification settings - Fork 230
Project: Refactoring Ring and RingElement
Work in progress, current document written by Jay Yang building on a discussion with Michael Stillman. Comments and contributions welcome.
Broadly speaking I have the following goals in this proposal in approximate order of priority:
- Make the code more exception safe
- No performance losses
- Document the actual Ring/RingElement/ARing interface
- Make the code easier to use correctly (fewer memory leaks)
- Make the code more like C++ code and less like C code
- Faster (or at least not slower) compile times
Everything on the public side is garbage collected.
Both RingElement
and Ring
classes are (and must be) pure virtual
Note we don't directly inherit from EngineObject RingElement is pure virtual, we can have implementations inherit from either EngineObject or if needed MutableEngineObject.
class RingElement{
public:
//pure virtual functions
virtual bool is_unit() const = 0;
//I'm torn whether operator notation is actually helpful for us
//the type returned is "wrong" such that we can't write a*b*c
virtual RingElement* operator*(const RingElement& other) const = 0;
//i.e. does the following read better or worse a->mult(b)
virtual RingElement* mult(const RingELement* other) const = 0;
...
};
class Ring{
public:
virtual ~Ring() = 0;
//pure virtual funtions
virtual RingElement from_int(int i) const = 0;
...
};
The instances of ring might need to be public. On the otherhand, we might be able to get away with factory functions. So either we have classes like this as part of the public interface
template<class R>
class ConcreteRing<R> : public Ring, public MutableEngineObject{
...
};
Or we make functions like this part of the public interface
Ring *makeZZp(int p);
Ring *makePolynomialRing(...);
We will also have an internal interface that engine code that manipulates RingElement and Ring use.
We have a templated type RingElementImpl that implements the actual code for RingElement. But we don't expect/need an default implementation.
template<class R>
class RingElementImpl<R> : public RingElement, public EngineObject{
//no default implementation
}
Instead we have specializations for each ring that detail the actual structure. It should be approximately as follows
template<class RT>
class RingElementImpl<ConcreteRing<RT> > : public RingElement, public EngineObject{
private:
const ConcreteRing<R> ˚
R::ElementType val;
public:
//actual implementations of the functions in RingElement
};
class RingInterface{
public:
//substitute whatever appropriate type for long
typedef long ElementType;
//This is a intended to be a zero cost wrapper around the C type.
//Importantly, by having an initializer, it follows
//RAII principles and is more exception safe.
//Note that in general a default constructor is not possible, so for arrays
//placement new will be needed.
struct Element{
public:
//this allows using Element (nearly) transparently for C code that expects ElementType
operator const ElementType&() const;
operator ValueType&();
explicit Element(const RingInterface& ri);//initialize as appropriate
//Be careful about adding copy constructors, it's not usually useful
Element(ElementType&& v);//allow moves (otherwise returning from functions is hard)
~Element();//this should infact cleanup the type
private:
ValueType value;
};
//I would have liked to have the following simpler signature, but it's
//not possible to do with zero extra cost
//Element add(const Element & a, const Element& b) const;
void add(ElementType& out, const ElementType& a, const ElementType& b) const;
//all the other arithmetic operations
//TODO think about conversion/initialization functions
}
Unless there's a good reason to, RingInterface instances should NOT be garbage collected, preferably, they will be direct members of the appropriate ConcreteRing class.
The justification for having RingInterface
and Ring
separate is so that code that does not need to use the frontend RingElement
can directly manipulate RingInterface::Element
instances.
Note that RingInterface::Element
replaces ARingElement<RI>
for most operations, but if the element needs to remember what ring it belongs to RingElementImpl<RI>
should be used instead.
There are 3 types that represent some sort of element of a ring
- RingElement
- ElementType
- Element
Each of these has a different role
- ElementType is the raw object understood by the underlying library or other code
- Element is a wrapper that makes ElementType exception safe
- RingElement is the object visible to the D code
In general, we should avoid direct uses of ElementType. However, references are allowed.
And the following inter-conversions are "free":
- RingElement& -> const ElementType&
- Element& -> ElementType&
Conversions to RingElement for more complex types requires a deep copy into GC memory:
- Element -> RingElement
- ElementType -> RingElement
Nothing major needs to change here, but for that we have something like this. The templates are not exposed, so the C interface is mostly straightforward
struct Ring;
struct RingElement;
//function prototype examples
Ring *makeRing(...);
RingElement *makeRingElement(Ring* r,...);
RingElement *add(const RingElement *a, const RingElement *b);
Ring *makePolynomialRing(Ring *coeff,...);
This is a proposed implementation strategy.
The goal here is to refactor all RingInterfaces instances to follow the template outlined above. This will involve changing most of the uses of ElementType. This should be performance neutral if done correctly, and will solve most of the exception safety issues related to RingElements. And while invasive from a lines of code perspective, it doesn't fundamentally change how any of the code works
Add a shim layer on top of the current code implementing the desired c++ interface. This will obviously be bad for performance, but this will test if the interface proposed is usable
The goal here is to remove the somewhat messy ring_elem
union. This will involve actually implementing RingElementImpl<R>
for all the rings. This change should get most of the performance lost in step 2 back
As a consequence of the previous steps, functions and implementations might end up in inconsistent places. The goal here is to have a consistent idea of where a function should go and follow that.
This new code is more template heavy overall, and so more care needs to be taken to ensure that the templates don't cause long compilation times.
It's annoying not to be able to default construct RingInterface::ElementType
objects, but this is needed for correctness in the general case. In particular this means that arrays of RingInterface::ElementType
either needs special support functions or placement new.
It's not clear that everything can be written as a ConcreteRing<R>
without resorting to specialization. Polynomial rings in particular are non-obvious.
There are 3 current "ARing" types which do not allow for a zero cost Element wrapper over ElementType, they are:
- ARingTower
- ARingGFFlint
- ARingGFFlintBig
For each of these, the problem lies in the destructor. Both of the ARingGF* types can theoretically be implemented, but it would require circumventing the public API of flint. For ARingTower it is impossible to create a zero cost wrapper as currently implemented. But ARingTower seems to have memory weirdness anyways.
We need to be slightly careful with multiple inheritance, especially when passing objects into C code.
Is it possible to move the ring element stuff into a separate namespace/directory? i.e. separate the concern of translating between M2 and C++ with the concern of actually doing math.
Currently integers and other "numbers" work differently than RingElements, A question is whether they should be made to be RingElements.
Because there isn't this ring_elem intermediary, we can probably give RingElement a finalizer, but there is a serious question about cost. In particular, how expensive are finializers really?
Finalizers are really expensive, but the disclaim system is much faster.
if we have two RawRingElement
a,b at the d level, assume then are of some ConcreteRing<RT>
instance
a*b
-
RingElement::operator*
(in relem.cpp) -
Ring::mult
(virtual) -
ConcreteRing<RT>::mult
(in aring-glue.hpp) -
RT::mult
(in aring-*.hpp depending on RT)
"New" multiplication process
a*b
-
RingElement::operator*
(virtual) RingElementImpl<ConcreteRing<RT>>::operator*
RT::mult
This has the same number of virtual function calls, which are probably the main expensive step.
Homepage | Projects | Packages | Documentation | Events | Google Group