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.
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.
> 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.
> value. And main value of things like Tree is that they
> work and can be used when needed. Anything that brings
> potential bugs _decreases_ value of such low-use code.
>
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
