Overheads when using structures?

[Stiffler]

Are there (significant) overheads for using structures?

Suppose we wish to store a very large number of facts like:
  person(name(surname, firstname), date_of_birth(dd, mm, yyyy)).

Are the predicate names 'name' and 'date_of_birth' being stored repeatedly?  Is it more efficient to flatten the structure to:
  person(surname,firstname,dd,mm,yyyy)

Is indexing affected by the structure?

Also, do the overheads depend on the prolog implementation used?

Many thanks,
PJ
_________________________________________________________________
Get inspired - dream, research, plan and book your next holiday online with MSN NZ Travel
http://a.ninemsn.com.au/b.aspx?URL=http%3A%2F%2Ftravel%2Emsn%2Eco%2Enz&_t=771497011&_r=MSN_NZ_travel_hmtagline&_m=EXT
------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Jan Wielemaker]

On Friday 25 April 2008 16:22, Parker Jones wrote:
> Are there (significant) overheads for using structures?
>
> Suppose we wish to store a very large number of facts like:
>   person(name(surname, firstname), date_of_birth(dd, mm, yyyy)).
>
> Are the predicate names 'name' and 'date_of_birth' being stored repeatedly?

The only predicate name here is person.  name and date_of_birth are merely
terms.  And yes, they are stored repeatedly.  It won't be dramatic in the
storage requirements though but ...

> Is it more efficient to flatten the structure to:
> person(surname,firstname,dd,mm,yyyy)
>
> Is indexing affected by the structure?

SWI-Prolog indexing is `base-line': first argument, using atomic constants
or name+arity of a term.  So, each clause is indexed on name+2 in the first
example, and surname in the second.  I think that makes the choice easy :-)

Sometimes the first is a lot nicer to handle in the application, which
is trivially solved using

person(name(Surname, Firstname), date_of_birth(DD, MM, YYYY)) :-
        person(Surname, Firstname, DD, MM, YYYY).

Now you have nice indexing and no space overhead (except for the
one clause above).

> Also, do the overheads depend on the prolog implementation used?

Space-wise, not very much. Some systems can index inside terms, either
specified by the user or dynamically, inferred from usage patterns.

With some fantasy you can do more enhanced indexing using term_hash/2 or
term_hash/4 (latest development source; stable version only has
hash_term/2).

        Cheers --- Jan


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Stiffler]

----------------------------------------

> From: wielemak@...
> To: prolog@...
> Subject: Re: [SWIPL] Overheads when using structures?
> Date: Fri, 25 Apr 2008 16:39:49 +0200
>
> On Friday 25 April 2008 16:22, Parker Jones wrote:
> > Are there (significant) overheads for using structures?
> >
> > Suppose we wish to store a very large number of facts like:
> >   person(name(surname, firstname), date_of_birth(dd, mm, yyyy)).
> >
> > Are the predicate names 'name' and 'date_of_birth' being stored repeatedly?
>
> The only predicate name here is person.  name and date_of_birth are merely
> terms.  

Yes of course.

> > Is it more efficient to flatten the structure to:
> > person(surname,firstname,dd,mm,yyyy)
> >
> > Is indexing affected by the structure?
>
> SWI-Prolog indexing is `base-line': first argument, using atomic constants
> or name+arity of a term.  So, each clause is indexed on name+2 in the first
> example, and surname in the second.  I think that makes the choice easy :-)

Indeed, the former is no help at all.

> Sometimes the first is a lot nicer to handle in the application, which
> is trivially solved using
>
> person(name(Surname, Firstname), date_of_birth(DD, MM, YYYY)) :-
> person(Surname, Firstname, DD, MM, YYYY).
>
> Now you have nice indexing and no space overhead (except for the
> one clause above).

That's very neat.  This definitely looks the way to go.

> > Also, do the overheads depend on the prolog implementation used?
>
> Space-wise, not very much. Some systems can index inside terms, either
> specified by the user or dynamically, inferred from usage patterns.
>
> With some fantasy you can do more enhanced indexing using term_hash/2 or
> term_hash/4 (latest development source; stable version only has
> hash_term/2).

That's good to know.  If this part of my code turns out to be on the critical path I'll certianly give term hashing a try.

Thanks for the help, Jan, and have a good weekend.
Cheers,
PJ
_________________________________________________________________
Find singles in your area with Match.
http://a.ninemsn.com.au/b.aspx?URL=http%3A%2F%2Fmatch%2Enz%2Emsn%2Ecom%2Fchannel%2Findex%2Easpx%3Ftrackingid%3D1043416&_r=WL_EMAL_TAG&_m=EXT
------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...