oldk1331 wrote:
>
> On 12/11/18 3:55 AM, Waldek Hebisch wrote:
> > oldk1331 wrote:
> >>
> >> This patch changes the Rep of Tree from
> >> Union(node:Record(value: S, args: List %),empty:"empty")
> >> to
> >> Record(val : S, args: List %)
> >> and uses "NIL$Lisp" to represent empty tree.
> >>
> >> Before this patch,
> >>
> >> (1) -> tree [1,2,3] pretend SEX
> >>
> >> (1) (0 1 (0 2) (0 3))
> >>
> >> And after:
> >>
> >> (1) -> tree [1,2,3] pretend SEX
> >>
> >> (1) (1 (2) (3))
> >>
> >> So this patch can save some (maybe a third) memory.
> >
> > Sorry that I did not comment earlier: this kind of change is
> > very dangerous. Namely, it can work quite nice in testing
> > and then lead to error say 3 years later. The point is
> > that there is correspondence between FriCAS types and
> > Lisp representation. Part of this correspondence are
> > known to Spad compiler and (via declarations) transmited to
> > Lisp compiler. So Lisp compiler is told that effectively
> > Record never is NIL. Breaking this can lead to nasty
> > errors when valid optimization is breaking "working" code.
>
> What if we do not use Rep, but use rep/per to trick the
> compiler? Then the compiler will not know about underlying
> representation and give them declaration.
rep/per alone solves almost nothing. The main problem is in
operations. You would need to add new set of primitives
consistent with desired representation at Lisp level.
For example, U32Vector is represented by Lisp array, but
of specialized type. Declarations present in operations
for U32Vector are invalid for other arrays and operations
for other arrays would be invalid for U32Vector.
So you can use different representation, provided that
it is done in consistent way and down to level of
primitives.
>
> I'm also writing a DoublyLinkedList Domain using:
> Rep := Record(val : S, next : %, prev : %)
>
> If I change that Rep to
> Union(node:Record(val : S, next : %, prev : %),empty:"empty")
>
> Then the code will not only be much slower but also be much
> more verbose:
>
> You can no longer access the "next" and "prev" pointer directly,
> you have to check for empty case every time.
Well, one can do one of the following:
- dully implement genric pattern (with checks for empty)
- only implement non empty case _and_ do not make it an aggregate
- use specialized representation with needed primitives
> > Let me add that Spad compiler contained (I would have to check
> > if it still contain) code to optimize unions in way you are
> > trying to do, namely avoid wrapper and tags in case when
> > Lisp types are disjoint. Activationg this code would
> > give large memory savings for several important types.
> > But it would also mean that we need make sure that
> > optimization is used only when it is valid and that
> > declarations in generated Lisp code match. There
> > is also question of runtime performance: smaller
> > memory use can give large speedups, but without declaration
> > at Lisp level code must contain more checks. So
> > there is delicate balance, small examples probably
> > would be slower while large would gain. Anyway, when
> > I looked at this my conclusion was that we do not
> > have developement resources to go in this direction.
> > Simply, we already have too many bugs to add optimizations
> > which are likely to bring more bugs.
> >
> > Concerning Tree, it has little use, so bugs here have less
> > impact. But by the same logic optimizing Tree adds little
>
> Well, by improving Tree, my next target is to improve BinaryTree,
> which use Tree as Rep. Next, maybe Red-black tree, and use that
> as Rep of Set. I think these are important data structures
> and should be optimized.
Well, Tree as a representaion of BinaryTree is already suboptimal.
BinaryTree as a representation of balanced trees again adds
overhead. If we want fast and efficient search tree we should
use specialized representation.
Note that given inheritance chain you propose empty set
would be represented as empty tree, so disallowing empty tree
would break inheritance at first place.
Concerning Set it is not so clear for me what to do with
representation. From point of view of memory use arrays
are more efficient (OK, list of arrays would be most
compact). For small sets lists are almost as good and
for small sets using lists gives quite good speed with
rather short code. In ordered case arrays could give
comparable or better search speed compared to balanced
trees, faster merge but slow insertion.
More generaly, for many special cases specializing code
and data structures could give us gains. Problem is
that currently automatic specialization of data structures
is inpractical and even explicit specialization by
programmer has rather poor support (in a sense C++ has
best known support for this, but IMO trying to emulate
C++ here is not wise). So specialization brings
cost of extra/duplicated code and growing complexity.
Complexity means more bugs, possibly up to the point of
program becoming unusable. In case of FriCAS the main
theme was to have generic code and data structures,
which are way slower and need more space than special
purpose versions. But this generic code is supposed to
be there ready to be used -- having slow code solving
a problem is much better than having no code at all.
In some cases generic code gives actually quite
good performance (mainly when most work is done by
specialized code in lower layers). In cases which
get a lot of use we provide specialized versions.
But this is done mostly based on measurements of
real tasks. For example, work on guessing package
showed that several basic routines were too slow
(and we replaced them by faster versions). But
one needs to be conservative here: in few cases
what first looked as improvement turned out to be
slower than existing code.
Coming back to trees: I think that we need fast seach
trees, but that they need separate representation,
different from other trees. I have doubts about replacing
representation of sets, for me it looks more resonable
to use search trees directly or possibly via a separate
domain say 'TreeBackedSet'.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
