On Fri, Sep 15, 2017 at 4:39 PM, Ralf Hemmecke <[email protected]> wrote:
> Thinking a bit about this... It's not all that bad. Yes, it goes through
> the list twice, but the overhead of keeping and updating an additional
> variable pointing to the end of the list (in the algorithm I described
> above) is probably also a factor of 2.
Yes, I did an experiment on this before, "keeping the last node" and
"traversing to do NREVERSE" takes the same amount of time.
> So, doing something twice is not always that bad. The question is how
> good is the memory management of FriCAS. Clearly, if (in the
> trunk-version of subtractIfCan) the allocated
>
> w := new(dim, 0)$Vector(R)
>
> is not returned (i.e. it fails), the vector should immediately be
> released back to the memory manager so that almost no time is needed if
> the next subtractIfCan creates a new vector.
The problem is that allocing memory involves system call which may
be time consuming, and Lisp has Garbage Collection which happens
periodically.
> Well, currently FriCAS is pretty much sequential. So one could make a
> preallocation of a couple of vectors during domain instantiation and use
> them as a temporary store. It would, however, become a problem, if
> FriCAS is able to use more than one processor.
>
> I could imaging the following, though.
> DirectProduct(n, T) has a (local) variable
>
> allocatedVectors: List %
>
> which collects such vectors like the w from above if subtractIfCan ends
> in "failed". The function "new" would have to be reprogrammed to first
> inspect allocatedVectors an take the vector from there.
> Well, that requires a bit of discipline from the programmer to correctly
> "release" unused vectors to "allocatedVectors". No idea whether that is
> a good suggestion.
Your idea is good, but it's complicated for Vector because it doesn't have
fixed length, for DirectProduct, it's simple because it's fixed length,
a simple local variable will do. And in the Groebner basis computation,
it uses DirectProduct.
tmp := 0$%
subtractIfCan(u:%, v:%):Union(%,"failed") ==
for i in 1..dim repeat
(c := subtractIfCan(qelt(u, i)$Rep, qelt(v,i)$Rep)) case "failed" =>
return "failed"
qsetelt!(tmp, i, c::R)$Rep
copy tmp
As for Vector, strictly speaking, it should not be able to add or subtract,
it doesn't have a fixed length, it's not AbelianGroup, just like List.
So I wouldn't worry about performance of subtractIfCan$Vector, people
should always use subtractIfCan$DirectProduct if they care about speed.
> Correct me if I'm wrong, but Aldor's memory management was divided in
> several parts. If memory was given back, it was collected according to
> its size, so a new allocation wouldn't have the need to claim memory
> from the operating system, but rather use the old data allocation.
>
> I'm not sure that there was something for arrays, but I guess, somthing
> similar would help. However, that's not so easy to program, because only
> the garbage collector in FriCAS knows when a vector is not referenced
> anymore. Otherwise, one would have to introduce a
> "releaseMemoryOfVariable(...)" and that would certainly add another pain
> to programmers.
Even if this mechanism exists for Lisp, it would vary from implementation
to implementation. I would suggest that programmer should avoid alloc
unnecessary memory in the first place.
You suggestion sounds like "memory pool", it might be useful for some
other domains.
> Oh, I would suggest "subtract: (%, %) -> %" so that subtract(x,y)
> returns z such that x = y + z if such a z exists (maybe one should
> require that the z is unique?). Otherwise it does whatever it likes (for
> example, delete the harddisk) or simply return an error, i.e. subtract
> should (by specification) only be applied if it is known that
> subtractIfCan does not return "failed".
>
> Why "subtract" and not "subtractIfCan2"?
> Well search for "IfCan" in the sources. I have the impression that for
> "fooIfCan" functions with signature Union(T, "failed") there is often a
> function foo with return type T. Best example is retract/retractIfCan.
>
> I wouldn't call such function "-", because one pretty much expects that
> "-" never fails. But that's not a very convinced opinion, only that
> subtract and subtractIf can better fits into the existing pattern.
>
> Ralf
One might expect that 'subtract' never fails. I think we should choose
between 'subtractIf' or 'subtractCan'.
--
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.
