Subject: RE: [hackers-il] "On Lisp" now available online for download

From: Omer Musaev <[email-masked]>
Date: Tue, 5 Feb 2002 14:52:05 +0200

> -----Original Message-----
> From: Oleg Goldshmidt [mailto:[email-masked]]
> Sent: Tuesday, February 05, 2002 12:23 PM
> To: [email-masked]
> Subject: Re: [hackers-il] "On Lisp" now available online for download
> 
> 
> Chen Shapira <[email-masked]> writes:
> 
> > But some things are more deceptive "Fundamental Algorithms in C++"
> > sounds pretty good, you actually have to read it to figure out that
> > it doesn't use the more interesting features of C++, which are
> > actually quite usefull when you code algorithms.
> 
> I have been under the impression that a good reference for
> _fundamental_ algorithms in C++ is "Generic Programming and STL" ;-).
> Is OmerM is at a shouting distance from you to confirm or deny that?..
> 
Yes, it is a nice introduction to STL/_most_fundamental algorithms.

However, while "Fundamental Algorithms in C++" covers algorithms that are 
taught in universities, STL <algorithm>s are more tools than algorithms.

According[1] to Alex Stepanov ( architect of STL ), he intended to insert
most common
CS algorithms into STL, but was confronted by Bjarne Stroustruppe, who
demanded 
STL to be as compact and orthogonal as it can be. Actually, due to political

disputations in Standard comittee, some more esoteric features entered the 
library, while some basic ones ( most notably hash ) are absent.

However, since generic <programming> is very potent technique, it is pity
that 
there are so few standard solutions available in generic form. 

[1] http://www.stlport.org/resources/StepanovUSA.html

> -- 
> Oleg Goldshmidt | [email-masked] 
> "If it ain't broken, it has not got enough features yet."
> 
> ------------------------ Yahoo! Groups Sponsor 
> ---------------------~-->
> Sponsored by VeriSign - The Value of Trust
> When building an e-commerce site, you want to start with a
> secure foundation. Learn how with VeriSign's FREE Guide.
> http://us.click.yahoo.com/oCuuSA/XdiDAA/yigFAA/saFolB/TM
> --------------------------------------------------------------
> -------~->
> 
> To unsubscribe from this group, send an email to:
> [email-masked]
> 
>  
> 
> Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/ 
> 
>

---

From: Oleg Goldshmidt <[email-masked]>
Date: 05 Feb 2002 16:06:21 +0200

Omer Musaev <[email-masked]> writes:

> some more esoteric features entered the library, while some basic
> ones ( most notably hash ) are absent.

How many times have I missed that! It does come with gcc, but is not 
standard...

> [1] http://www.stlport.org/resources/StepanovUSA.html

There is a great passage there about Stepanov's early realization that
"agorithms are defined on algebraic structures". In my head, it echoes
the "show me your structures and the block diagram becomes irrelevant"
very nicely.

What does the hackers-il population think of Stepanov's criticism of
OOP?

"I have yet to see an interesting piece of code that comes from these
OO people." 

"...It might be a profitable thing for all your readers to learn Java,
but it has no intellectual value whatsoever."

What I did like was the "Money Oriented Programming" moniker ;-)

---

From: Shlomi Fish <[email-masked]>
Date: Wed, 6 Feb 2002 15:48:28 +0200 (IST)

> How many times have I missed that! It does come with gcc, but is not

I first thought that it was strange that STL lacked hashes. But then I
remembered something: hashing theory is very comprehensive and there are a
lot of ways to implement and tweak a hash. Points that come to mind:

1. Chaining vs. Open-Addressing.

2. The Hash function being chosen. (refer to:
http://burtleburtle.net/bob/hash/)

3. Modulo bucketing vs. multiplicative bucketing.

4. Re-hashing.

5. Storing the hash values next to the keys (to make for faster
comparisons and re-hashings)

6. Promoting or caching frequently accessed elements in the backets.

7. Using something other than a linked list as a bucket - a doubly-linked
list, a binary tree, a vector, another hash (;-) - I know someone who did
that because he did not know better),

8. Perfect Hashing.

9. Universal Hashing.

10. Which operations: an atomic check-if-exists and if not add? An atomic
check-and-replace, an insert-if-not-exist, etc.

---

When working on Freecell Solver, I noticed that my own hash performed
better than Glib's because I used better optimizations. I believe it would
have out-performed Glib's hash in most other cases. (Note - it's API is
still very incomplete, because of the requirements of FCS). Had I written
a Gtk+/GNOME app, I probably would have been "forced" to use it because
it's part of the Gtk+ architecture, which would have made the application
slower.

Some languages, like Perl, force a certain implementation (and a certain
hash function) on their users. In Perl at least, one can program
primitives that behave like hashes in Perl and in C, but they are not the
default. Mark-Jason Dominus demonstrates that the hash function can go
wrong:

http://perl.plover.com/#badhash

So basically the dilemma is what hash implementation to have, or what
range of hashing options to support. I'm not sure it is possible to build
a hash abstraction that would support all of the hashing options and will
not be too bloated or unmaintainable.

Had STL contained a hash, it would have been possible that some
programmers could have (and possibly rightfully) blamed their program's
performance on the hash. Since a hash is usually quite trivial to program,
it's, IMO, a good idea to sometimes use your own custom hash
implementation.

Regards,

	Shlomi Fish

There is no IGLU Cabal! They tried to save complexity and preferred to use
a hash over a balanced binary tree. They managed to insert all of the
elements in O(n) time, but then discovered it would take an extra
O(n*log(n)) to print them in order. This caused confusion and
disappointment and brought the demise of the cabal.

> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Arik Baratz <[email-masked]>
Date: Wed, 6 Feb 2002 21:14:13 +0000 (GMT)

online for download ]?=
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1

Hashes are application specific. A good hash is good in a specific situation -
that is, for each function f(x) of a random variable x there is a hash function
h(f(x)) that generates a uniform distribution.

If you want a catch-all hash function, use a cryptographic hash like MD5. If you
want a lean and mean function, you\'d have to analyze the domain you are working
with and think up a function that hashes it ok.

The glibc hash is very simplistic - you can beat it in many ways.

-- Arik

On 06.02.2002 at 15:49:49, Shlomi Fish <[email-masked]> wrote:

> better than Glib\'s because I used better optimizations. I believe it would
> have out-performed Glib\'s hash in most other cases. (Note - it\'s API is
> a Gtk+/GNOME app, I probably would have been \"forced\" to use it because
> it\'s part of the Gtk+ architecture, which would have made the application
> slower.
> 
> range of hashing options to support. I\'m not sure it is possible to build
> programmers could have (and possibly rightfully) blamed their program\'s
> it\'s, IMO, a good idea to sometimes use your own custom hash
> implementation.
> 
> Regards,
> 
> 	Shlomi Fish
> 
> > There is a great passage there about Stepanov\'s early realization that
> > \"agorithms are defined on algebraic structures\". In my head, it echoes
> > the \"show me your structures and the block diagram becomes irrelevant\"
> > very nicely.
> >
> > What does the hackers-il population think of Stepanov\'s criticism of
> > OOP?
> >
> > \"I have yet to see an interesting piece of code that comes from these
> > OO people.\"
> >
> > \"...It might be a profitable thing for all your readers to learn Java,
> > but it has no intellectual value whatsoever.\"
> >
> > What I did like was the \"Money Oriented Programming\" moniker ;-)
> >
> > --
> > \"If it ain\'t broken, it has not got enough features yet.\"
> >
> >
> \"Let\'s suppose you have a table with 2^n cups...\"
> \"Wait a second - is n a natural number?\"
> 
> 
> 

Arik Baratz
System Engineer
[email-masked]

Office:
4 Hamelacha St.
Raa&#8217;nana 43661
ISRAEL

Tel:    +972 (9) 743-9250 ext. 214
Fax:   +972 (9) 743-9251
Cell:  +972 (52) 354 959
eFax: +1 (978) 926-8913
ICQ:  210 8214

Privileged and / or confidential Information may be contained in this electronic
mail message. 

You may not copy or deliver this message to anyone without my consent.

If you are not the addressee indicated in this message, or you feel that this
message is not intended for you, Please destroy this message and kindly notify
the sender by replying to this electronic mail.

Please advise immediately if you or your employer do not agree to the use of
Internet email for messages of this kind.

Opinions, conclusions and other information in this message that do not relate
to the official business of Vidius shall be understood as neither given nor
endorsed by it.

---

From: Omer Zak <[email-masked]>
Date: Thu, 7 Feb 2002 00:32:04 +0200 (IST)

> 1. Chaining vs. Open-Addressing.

[... more options were snipped ...]

> it's, IMO, a good idea to sometimes use your own custom hash

On the other hand, let's not forget what I believe to be the reason for
FORTH's demise.  FORTH is a very elegant language, with unorthodox ideas.
It was invented by Chuck Moore, who is having his own eccentric (and
fresh) ideas about how one should program.

The reason FORTH didn't take hold (at least in my own projects) was that
it lacked standard libraries for the things which I needed.  It expected
people to reinvent the wheel (and optimize it to their project's needs)
all the time.  It didn't take to heart Pareto's Law (80% of the
computer time/programmer time/memory requirements/bug expenses of software
are in 20% of the code).  People should optimize and design their own
implementations of data structures only when and where they are critical
to the software's performance.  For non-critical parts of the software,
standard libraries are good enough and should be used.

The morale of the story to hash functions in STL:
STL should have provided a standard hash implementation (like Perl does).
But the standard implementation should (like implementations of all
other STL data structuers) have provisions for people to substitute their
optimized algorithms when those algorithms are really needed for a
specific application.
                                             --- Omer
There is no IGLU Cabal.  We'll organize the next meeting when we finish
to prove, from First Principles, that 1 + 1 = 2.
WARNING TO SPAMMERS:  see at http://www.zak.co.il/spamwarning.html

---

From: "Nadav Har'El" <[email-masked]>
Date: Thu, 7 Feb 2002 01:05:59 +0200

On Wed, Feb 06, 2002, Shlomi Fish wrote about "[hackers-il] To Hash or not to Hash [was Re: "On Lisp" now available online for download ]":
>...

When efficiency is the key, "canned" hash implementations are many times
not good enough. They waste memory when memory is important to you, they
are too slow when speed is important, the hash function doesn't work well
for your (weird) choice of keys, they don't have predictable run times
(e.g., one insert can take 1000 times of another insert, because your hash
spontaneously decided to grow and reorder itself), and a bunch of other
problems.

But when absolute efficiency and suiting the exact problem isn't needed,
a general-purpose hash is a very useful tool. Consider for example the
hashes in Perl or Awk. I've used them countless times. They let you do
very powerful stuff very easily. And I never cared if they are not
the most efficient solution possible.

So I think the STL *should* contain a hash, at least for keys with certain
simple types (integer arrays, strings, etc.). Someone who needs very special
implementations for very specific purposes will probably implement something
differet - but someone who just needs "something that works well" will be
happy with the STL's hash.

Other STL containers have similar tradeoffs as with hashes - consider, for
example, priority queues. STL's implementation are based on "heaps", and
have O(logn) insertion and pop. It's easy to write a different implementation
with a O(n) insertion of a whole sorted group of events and O(1) pop - such
implementation might be faster for special uses. It's possible to implement
hash-like O(1) insert and O(1) pop if you make other types of assumptions on
the distribution of events on the queue.
For example, in one program I once wrote in C++, where efficiency was of
utmost importance and required the use of priority queues in two places -
in one place the STL implementation was very good (better than something I
tried to write myself), but in another place, my O(1) implementation was
better.

In the same program I also needed a hashtable, and in that case two things
were very important: very low memory use and predictable time (no sudden
reorganizations of the hash), so the SGI's STL hash was not suitable at
all. I ended up writing a very optimized solution, that ended up taking
only about 6 bytes (if I remember correctly) per entry over the length of
the entry (key+value) itself, under certain assumption (one key assumption
that the hash table will never contain more than 2^16 entries).

-- 
Nadav Har'El                        |    Thursday, Feb  7 2002, 25 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |I want to live forever or die in the
http://nadav.harel.org.il           |attempt.

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 7 Feb 2002 03:03:11 +0200 (IST)

> optimized algorithms when those algorithms are really needed for a

Sounds like a good compromise. In any case, deriving a class from a base
hash class may make the code a bit more difficult but not much, assuming
the code makes use of hash<mytype> & instead of
my_own_efficient_hash<mytype> & (pardon my C++ and STL ignorance in case
it shows).

> to prove, from First Principles, that 1 + 1 = 2.

Purposely taking the joke too seriously:

I believe Russel and Whitham managed to prove arithmetics from logic in
"Prinicipa Mathematica". However, I believe 2 is defined as "1 + 1", or as
the number that follows one, even though it undoubtedly has much more
properties.

It's like the De-Morgan Laws (not(A and B) = not(A) or not(B) and vice
versa). One can show that they hold for every A and B and that's enough of
a proof. I am not referring to the general case (for A1, A2, A3, A4...)
that has to be proved by mathemtical induction.

Regards,

	Shlomi Fish

There is no IGLU Cabal! One of its most prominent members commited suicide
when he failed to find a proof that the axiom that "A is A, and A is not
not-A" holds for every A.

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 7 Feb 2002 08:24:05 +0200 (IST)

> h(f(x)) that generates a uniform distribution.

Actually if f(x) = C, where C is a constant, no such hash function exist
or can exist.

> If you want a catch-all hash function, use a cryptographic hash like MD5.

Have you ever tried running md5sum on a CD-ROM you just downloaded from
the Internet? It takes forever to run. Usually, one will prefer to use a
non-cryptographic hash function because it is faster and albeit can be
tricked, usually generates equally good results. If there are a limited
number of elements, than a Perfect Hash, which you'll have to compile from
the set, would probably be a better choice.

This is of course assuming the keys are fully serializable in some way.
Sometimes, preparing a serialized key is not very straightforward.

> If you

That was the case with Freecell Solver, where I recently switched from MD5
to Perl's hash function and did not notice too big a difference in the
speed.

However, the hash function being chosen is just one of the elements of
constructing a good hash (albeit a very important one, because a hash is
only as good as it). Refer to my previous posts for other elements like
chaining vs. open addressing, promoting or caching elements, etc. In C++,
I'm not sure how well can one re-use the chain's elements, when they are
re-hashed, and just pointing them to differnt elements, which is another
technique I used in FCS.

What I like about ANSI C, is that it does what you want when you want it,
and if you know what you're doing there are very little side-effects. It
does provide for a greater error ratio, than most other languages I know,
though.

> The glibc hash is very simplistic - you can beat it in many ways.

s/glibc/glib/? (glibc does not contain a hash, AFAI'm aware).

My point was that if you are working on a Gtk+/GNOME application, you are
stuck with the glib's hash whether you want it or not, because it's part
of the Gtk+/GNOME architecture. You can code your own hash in ANSI C, but
then you may be criticized for making the code unreadable, or deviating
from the Standard Way of Doing Things<tm> there. And in Glib's 1.2 at
least, I believe it's impossible to define a hash with the same interface
as Glib's hash, not to mention that the interface itself is not very
optimizied (or sensible).

Regards,

	Shlomi Fish

---

From: Arik Baratz <[email-masked]>
Date: Thu, 7 Feb 2002 18:53:51 +0000 (GMT)

ailable ]?=
MIME-Version: 1.0

> Actually if f(x) = C, where C is a constant, no such hash function exist

Oh yeah? how about f(x) = rand(seed)? Obviously, if f(x)=C, you might want to
use a data structure different than a hash anyways.
 
> number of elements, than a Perfect Hash, which you\'ll have to compile from

Actually I have just md5sum-ed a 2GB file, so I know how slow it is... I totaly
agree that baring special circumstances (i.e. in order to create the trapdoor
effect, say, in issuing confirmation numbers for flights, when the confirmation
cannot lead back to info in the ticket).

> > If you
> > want a lean and mean function, you\\\'d have to analyze the domain you are
working
> to Perl\'s hash function and did not notice too big a difference in the
> speed.
> 
> I\'m not sure how well can one re-use the chain\'s elements, when they are
> and if you know what you\'re doing there are very little side-effects. It
> s/glibc/glib/? (glibc does not contain a hash, AFAI\'m aware).

yes

> stuck with the glib\'s hash whether you want it or not, because it\'s part
> from the Standard Way of Doing Things<tm> there. And in Glib\'s 1.2 at
> least, I believe it\'s impossible to define a hash with the same interface
> as Glib\'s hash, not to mention that the interface itself is not very

Well, the SWoDT is not always the best, and you ought not always to listen to
what other people say about your style. Well, maybe listen, but not always
embrace.

-- Arik

---

From: "Nadav Har'El" <[email-masked]>
Date: Thu, 7 Feb 2002 21:17:39 +0200

> Content-Type: text/plain; charset=iso-8859-1

Wow, something is *REALLY* wrong with your mail program, Vidius filter,
or whatever... A part of the the subject got hacked off into the main
text (as you can see in the quote above), 

> > to Perl\'s hash function and did not notice too big a difference in the

and something caused all single quotes in your message (even its subject line)
to be backslashed, sometimes by more than one backslash. What is this - a
mailer written in a shell? :)

Weird ;)

-- 
Nadav Har'El                        |    Thursday, Feb  7 2002, 26 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |I before E except after C. We live in a
http://nadav.harel.org.il           |weird society!

---

From: Arik Baratz <[email-masked]>
Date: Thu, 7 Feb 2002 20:32:22 +0000 (GMT)

\\\\\\"On Lisp\\\\\\\" now av=3D?=
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1

On 07.02.2002 at 21:18:58, Nadav Har\'El <[email-masked]> wrote:

> On Thu, Feb 07, 2002, Arik Baratz wrote about \"=?iso-8859-1?Q?Re:
[hackers-il] Re: To Hash or not to Hash [was Re: \\\\\\\"On Lisp\\\\\\\" now
> text (as you can see in the quote above), 

I\'m in the united states right now, and I\'m using JawMail
http://jawmail.sf.net beta version. It has some flaws, I admit.
> 
> > > > want a lean and mean function, you\\\\\\\'d have to analyze the domain
you are
> > > to Perl\\\'s hash function and did not notice too big a difference in
the
> mailer written in a shell? :)

Not in shell, in PHP. It\'s somewhat buggy, but it works...

Arik Baratz
System Engineer
[email-masked]

Office:
4 Hamelacha St.
Raa&#8217;nana 43661
ISRAEL

---

From: mulix <[email-masked]>
Date: Thu, 7 Feb 2002 22:36:36 +0200 (IST)

> Content-Type: text/plain; charset=iso-8859-1

[snipped other such monstrosities, and then arik said]
> Not in shell, in PHP. It\'s somewhat buggy, but it works...

egads, whatever happened to good ol' telnet my.mail.server.com 25 and
talking SMTP like reasonable human beings?

ObHackersIL - nothing. things have certainly hit a low point.
-- 
mulix

http://vipe.technion.ac.il/~mulix/
http://syscalltrack.sf.net/