I am using hash-tables, and realized that Lisp, by the way hash-tables are
defined, must store the keys of the hash-table.  I am trying to run something
which quickly starts sucking up memory because storing all the keys is
heinus.  I'd rather just have collisions, in which case I have a novel way to
resolve them.  I'm trying to figure out a way out.

The idea is pretty simple and probably generic:

instead of using (setf gethash) to insert, I'll use pushnew + (setf gethash)
and for instead of using gethash I'll use find + gethash.  that way I can make
my own hash-table, but somehow using keys which don't necessary suck up as
much memory for storage as what I'd originally wanted.

does this make sense to anyone?  I'm sure poeple have, at some point in time,
wanted a more relaxed version of hash-tables which don't guarantee "no
collisions", and (maybe) one for which you cannot iterate over the keys.
Anyone have a clue here?

(defun make-table (size)
  (make-array size  :initial-element nil))

(defun get-value (key table)
  (svref table (mod (sxhash key) (length table))))

(defun (setf get-value) (value key table)
  (setf (svref table (mod (sxhash key) (length table))) value))

  Two other responses have point out the function  SXHASH.
  However, this doesn't guarrantee unique values for each object.
  You would still need the key to resolve collisions.  For example:

USER(11): (sxhash #( a b ))
2
USER(12): (sxhash #( c d ))
2

   Here the impelementation is apparently returning the size of the vector
   as the code.  For other data types the values distribution is much more
   less uniform. :-)  [ It is implementation specific on how well the
   hash codes are distributed over all possible values.  The restriction
   the codes be indepedent of an "image" likely means for some
   situations it will be far from "perfect". ]

   What I think you are looking for is a "perfect hashing" function.
   In some circumstances you can create these.  See Knuth (or another good
   algorithms book) on perfect hashes.  If each hash code is unique
   then you don't need to store the keys to resolve collisions.  Because
   there aren't any and the index into the underlying array is  the
   "key".

   [ Another partial solution would be to only store the keys for
      the cases where SXHASH did produce a solution.  Although in
      the worst case everything could collide and you'd have an
      even larger "problem". ]

   And I'm not sure what you mean by iterate over the keys.
   You can iterate over a hash table ( this iteration process is
   independent of the keys).  MAPHASH and WITH-HASH-TABLE-ITERATOR
   iterate over the table but there is no "order" in which the
   keys are encouttered.

--

  I also wondered if this memory growth problem was that the keys never got
  flushed. Garbage collection is nice, but with non-ephemeral hash tables
  you have to explicity flush the key->data mapping once you are done with
  it. [ Unless you have weak tables. ]

--

suppose, ideally, I want a hash table whose keys are strings and whose
values are objects.  However, I have so many keys, and each key (string)
is, say 50 characters long.  With 50,000 keys, this can start to really
swallow up memory.  But if, instead, the objects in the hash buckets
somehow contain the strings efficiently, then I can create those strings
when needed, but not store them permanently.

If you're wondering how that can be done, just imagine that two numbers
(pos . length) specifiy a sub-string inside one huge string.  So just
storing the pos and length is enough.

* to pass just one object to the hash table when you do the store
  (instead of one key and one object, as with CL);

* to pass a function to the hash table constructor which will later
  be called on each object being stored to compute the key.

Unless someone has already implemented such tables somewhere,
it is up to you.

Good luck,
Vassil.

Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

  I'd like to see the actual size of the application that needs this kind
  of anal-retentive "efficiency" tinkering.  I have an application that I
  thought would gobble up all available memory in production, so I wrote a
  little thing using SLOT-UNBOUND that gave me lazy-loaded messages that
  could be "unloaded" and read back from disk on demand, and prepared to
  tie this into GC hooks and all.  a message is between 100 bytes and 40K
  long, and contains a _lot_ of structure, so the 100-byte message conses
  about 1K and the 40K message about 44K.  there are approximately 350 of
  them per day, 5 days a week today.  there will be approximately 3000 of
  them per day at the end of this month, albeit the increase will be in
  very small messages.  the machine has only 64M RAM, so I worried a bit.
  a test run of 15000 evenly paced messages (so GC could run near normally
  and tenure these bastards at a normal pace) caused Allegro CL to swell to
  34M RAM.  it was no problem at all.  the SLOT-UNBOUND stuff is useful for
  a lot of other reasons, so it wasn't a waste of time, but UNLOAD-MESSAGE
  never gets called in the production version.  the part of my brain that
  still remembers when I thought C was a programming language had voiced
  its usual misguided protests.  a C programmer would have worried that 34M
  was a lot of wasted memory.  after all, the active lifetime of a message
  averages out at 15 seconds, but worst case, it's hanging around in memory
  for a week, just because some client _may_ want an old copy of it.  the
  optimization problem is basically this: it would cost more to figure out
  when to unload these messages than I would ever hope to save by doing so
  and since the memory is not used for anything else, _any_ time spent on
  figuring out when to unload would be a waste, and the occasional load
  would _also_ be a loss.  still, I'll bet a C programmer would cringe at
  the "inefficiency" of having more or less dead objects take up many
  megabytes of RAM for a whole week, but what would I do with it?  (it's
  not like I run Windows or anything.)

  the hardest part for a programmer used to C and C++ and that crap is to
  shed the _invalid_ concerns.  psychologists call them "obsessions" and
  charge people a lot to get rid of them.  some programmers charge their
  users a lot to be able to keep them.  go figure.

In the actual case that I'm working on, there is an optimal way to store
the data (compressed, in the Huffman sense, which would require
probabilistic analysis, etc).  I'm just doing something in-between.
Though I'm probably sweating a lot on this now, it's so that I don't
have to sweat later, and thus, I'm being lazy.  I don't want to
re-design later.

Still, after reading your few posts-of-the-day (and Kent's) I think that
the best way is to take advantage of CLOS, and do it inefficiently now,
and then, if it needs to be tweaked later, I should be able to fix it
w/o changing the interface to the class objects.  I guess this is how
all methods in CLOS are virtual.  I'd just have to make sure that in the
subsequent coding, I'll have to make sure to use `with-accessors'
instead of `with-slots'.  I don't know anymore.  When a programming task
requires you to swallow the 6+ Meg Brown corpus, and run recursively
optimal segmentation on it, I start to worry about storage.  I don't
think this is so crazy.  Plus, I've always used defstruct in the past.
I've always been reluctant to use CLOS.  I'll do what you suggest.  I
think you're probably right, since this stuff is sucking up wads of
time.  My girlfriend told me that last nite I said, in my sleep, "I
really don't understand object orientation in Lisp."  It's probably the
first complete sentence I've ever uttered in my sleep that was
gramatically and semantically correct.

CLOS does not do compile-time method resolution.

CLOS also does not necessarily take longer to find a method on a
parent class than a child class.  Effective method computation
is not doen every time you do dispatch, and once it is done, there
is no necessary inefficiency of finding the method that can be
described as a cost in terms of distance between the actual class
and the class being inherited from in the type tree.

As to using defstruct instead of defclass, there are sometimes reasons
for doing this.  But they are very few.  In general, the only
difference there will be constant factors in speed, and if all that
stands between you and a perfect product is constant factors on that
order of magnitude, you're going to be well ahead of the game.
Further, using defclass gives you good leverage that will help assure
you are far enough along in your work that it'll be worth caring about
performance.  Using defstruct, except as an after-the-fact
optimization to accomodate an observed make-or-break efficiency
problem that is specifically proven to be making a complete product
unacceptably slow is very suspect.

There are circumstances where resolving colisions doesn't require
knowing the keys.

--
Kenneth P. Turvey <ktur...@SprocketShop.com>

But still, if I had this:

(defclass city () ((name :accessor name)))
(defclass person () ((name :accessor name)))

(defmethod city-with-same-name-as-person ((p person))
  (with-accessors ((pname name)) p
    (loop for city of-type city in *cities*
      until (string= name (name city))
      finally (return city))))

Now, wouldn't it be nice if #'name in (name city) could take advantage
of the fact that it knew that its argument was a subtype of city?  Maybe
this argument isn't so concrete, but if you note that CLOS dispatches on
the types of multiple arguments, then you'll see how compile-time method
resolution can be (at least partially) computed.  i.e. you have
something like:

(defmethod f ((a type-1) (b type-1)) ...)
(defmethod f ((a type-1) (b type 2)) ...)
(defmethod f ((a type-2) (b type-1)) ...)
(defmethod f ((a type-2) (b type-2)) ...)

Then if a declaration in another method told you that `a' was of-type
`type-2', then you'd only have to check the type of `b' at run-time.

But, of course, with the dynamism of CL, this might be in conflict with
run-time class- and method-definition.

(defun make-keyless-hash () (make-array 20))

(defun gethash (key table)
 (aref table (mod (sxhash key) (length table)))))

(defun sethash (value key table)
 (push value (aref table (mod (sxhash key) (length table)))))

If you make the table big enough and the hash values distribute
well, you might be ok.
Another hack is to use a "sparse matrix" array if the hash keys
are highly distributed, that is, make the "array" huge, but don't
actually create the whole table until needed, below the
array is 65,535 elements large.

see http://www.intellimarket.com/oodb/keyless.cl

(sethash a 'foo *hash-table*)
(sethash b 'foo *hash-table*)
(gethash 'foo *hash-table*)

  I'd have expected the answer to be b, not (b a). I personally would have
wrtten it so that if a collision happens, the last one wins, aka:

(defun sethash (value key table)
  (setf (aref table (mod (sxhash key) (length table))) value))

(sethash a 'foo *hash-table*)
(gethash 'baz *hash-table*)

    Then the  latter expression will return the entry for FOO.  I
    would presume that this is an error, not a feature.

    IHMO, only in extremely special circumstances can you not include
    the key (or an "alias" thereof) along with the value in the hash table
    entry.  Specifically, when there are unique hash buckets for each
    possible entry, the bucket "index" can serve as the key.  This
    index may not be an effective "alias" if you every wish to reverse
    index the key.

    SXHASH doesn't intentially  provide this property. ( it may happend to
    work on a specific implementation in a specific context. )

--

[ sound advice elided ]

Regs, Pierre.

PS: Last time I looked, the book was available via amazon.com.

(defclass wonderful-city (city) ())

(defmethod city :around ((self wonderful-city))
  (format nil "The wonderful city of ~A" (next-method)))

Most optimizations that were done to (name city) would probably not work on
objects of class wonderful-city.  It might help if the implementation of
method dispatch were some kind of search through the class hierarchy, since
it would give you a starting point in the tree; but that's not generally
how dispatching is implemented, so the hint doesn't really help.

  well, there's constructive laziness and there's careless laziness.

| A lazy person that was still determined to complete a hard task would
| tend to do it in a way that was quick, efficient, and that would minimize
| energy consumption over the usage of that program, meaning that his/her
| program would be extensible as far as he/she could have forcasted
| initially.

  sure.  one way to accomplish this is not to worry about needless things.

| I don't want to re-design later.

  but you will.  you don't know enough about the _real_ efficiency issues
  at this early time to make the right design choices.  trust me on this.

| I guess this is how all methods in CLOS are virtual.

  you're being carelessly lazy, yet you don't appear to see it.  "virtual"
  doesn't exist in the CLOS vocabulary.  you show that you don't understand
  CLOS by using terms that are meaningless in its context, and, moreover,
  you show that you don't care to do the _necessary_ work to understand
  what that differences are all about.  this is not the good lzey.

| I'd just have to make sure that in the subsequent coding, I'll have to
| make sure to use `with-accessors' instead of `with-slots'.

  huh?

| When a programming task requires you to swallow the 6+ Meg Brown corpus,
| and run recursively optimal segmentation on it, I start to worry about
| storage.  I don't think this is so crazy.

  well, I don't think it's crazy to worry about, because that makes you
  spend more time on the important properties of storage efficiency, but
  obsessing about the unimportant issues _is_ crazy, and complaining about
  it before you know what's really a problem is definitely crazy.

  I've seen some horribly "efficient" code try to deal with large amounts
  of text, and it was just so badly done that _any_ change to it would mean
  a rewrite of major parts of the rest of the system.  these guys also
  argued vociferously about efficiency -- their report said they had to
  because they were severely limited in machine power.  so I rewrote their
  entire system just to see how much it would be pessimized by being more
  elegant.  (it took a few months of spare time, compared to the week I had
  envisioned when I started.)  well, the first rewrite took twice as long
  to run and used 10% more memory.  I profiled it, and I located some
  boneheaded duplication of effort, so I memoized a couple functions, which
  used another 10% more memory, but it used only 5% more CPU than the
  highly optimized code I had rewritten.  then I noticed that a lot of time
  was spent in the memoization code for one of the functions, and realized
  that memoization should be taken one step further: the whole relationship
  that was being computed was basically the same from run to run, and it
  was "learning" from more and more input.  they had tried to save that
  stuff to disk, but that was slower than training it anew, and it didn't
  really work, either.  so I made a *huge* array and used twice as much
  memory as the original code, but it ran in 75% of the time.  there was
  still ample room for improvement, and my 64M SPARC was not at all unhappy
  about the memory consumption.  once this relationship vector had proven
  to converge, it could indeed be stored more efficiently, at the cost of
  slightly more expensive updates, and one shot at that brought the memory
  size to 80% of the original program had spent on _its_ second round.

  I couldn't quite figure this out at the time, but it dawned me some time
  later: I was willing to be "temporarily inefficient", so I discovered a
  very different "optimization path" than the one where _every_ step was
  supposed to efficient.  it was about that time that I started to figure
  out why it is so tremendously hard to improve things in society, too: at
  every opportunity, people will optimize their observed political reality,
  and they become very good at it.  any significant improvement comes at
  such a high cost to everyone who has optimized their personal political
  reality that it takes a "revolution" to change almost anything.  stepwise
  refinements to this realization took the form of a desire to find the
  real constructive element in what keeps traditions around and what makes
  people "conservative", and I think I got it: "it was painful to get here,
  so if you change anything, it will be painful to make that as cozy as we
  have made this place".  that personal pain will far outweigh any real or
  projected benefits to any person or any part of the system.  I don't
  think this is a valid objection.  I also don't think "sacrifices" is a
  valid argument.  the point is to be secure and safe enough to be able to
  relinquish control for a short period of time and then regain it, maybe
  in a new or at least _slightly_ different form.

| Plus, I've always used defstruct in the past.  I've always been reluctant
| to use CLOS.

  why?  are you using CMUCL or CLISP or soemthing?  (I know I abhorred CLOS
  while I only had CMUCL and CLISP, and that's one reason why I don't think
  people should optimize for free software until they know what it should
  be like.  (with a Unix work-alike, that's pretty easy, since a child can
  see what's wrong with Unix and improve upon it.)  too often, they settle
  for what can be done without a lot of effort and only through incremental
  improvements.

  well, what is this purported single OOP vocabulary?  is it a denial of
  the fact that certain terms have meaning only in the context of specific
  languages?  does it make any more sense to talk about "virtual methods"
  in CLOS than it does to talk about "generic functions" in C++ just
  because there's multiple inheritance from "the C++ vocabulary" and "the
  CLOS vocabulary" into "the OOP vocabulary"?

| And in that context, all CLOS methods are virtual -- they dispatch on the
| dynamic type of the object, rather than the static type of a variable
| declaration.  Since CLOS doesn't provide non-virtual methods, it doesn't
| need a syntactic way to indicate which are virtual and non-virtual, as
| C++ does.

  great.  I'm sure you made him feel better for having been consoled and
  told "you're not completely wrong", and now he'll continue to talk about
  virtual functions in CLOS forever, instead of having the potential of
  being rewarded for getting it right some time in the future.  just great.

However, I've discovered from past conversations that you believe it's
totally wrong to make any references or analogies between programming
paradigms (it's come up in threads comparing Lisp and Perl, for instance).
In comp.lang.lisp we must act as if no other languages exist, and woe be
unto one who lapses and mentions a term they've learned in another
environment -- the wrath of Erik will be upon them.