Message-ID:

They are relatively good but absolutely terrible. -- Alan Kay, commenting on Apollos

devel / comp.lang.python / Re: Best practice for caching hash

Re: Best practice for caching hash

<mailman.311.1647387679.2329.python-list@python.org>

https://www.novabbs.com/devel/article-flat.php?id=17518&group=comp.lang.python#17518

copy link Newsgroups: comp.lang.python

Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: cs...@cskk.id.au (Cameron Simpson)
Newsgroups: comp.lang.python
Subject: Re: Best practice for caching hash
Date: Wed, 16 Mar 2022 08:32:37 +1100
Lines: 52
Message-ID: <mailman.311.1647387679.2329.python-list@python.org>
References: <CABbU2U9CwzB=ko_2n-QCG32MC3kn6R7R-m-TcOJZPPMWsULGxw@mail.gmail.com>
<YjEF9a4RRTjnEpBx@cskk.homeip.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: news.uni-berlin.de HpW54T/ZuRLgAOOyTTtuKwU/Cwzu8U74CrwMjjpdzxVw==
Return-Path: <cameron@cskk.id.au>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
Authentication-Results: mail.python.org; dkim=none reason="no signature";
dkim-adsp=none (unprotected policy); dkim-atps=neutral
X-Spam-Status: OK 0.001
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'url-ip:140.82.114.3/32':
0.03; 'url-ip:140.82.114/24': 0.03; 'url-ip:140.82/16': 0.03;
'traceback': 0.04; 'error:': 0.05; 'issue.': 0.05; 'cases.': 0.09;
'compute': 0.09; 'example:': 0.09; 'identical': 0.09; 'objects,':
0.09; 'typeerror:': 0.09; 'values.': 0.09; 'cheers,': 0.11;
'url:github': 0.14; 'url-ip:140/8': 0.15; '(it': 0.16; 'cameron':
0.16; 'dict': 0.16; 'exception.': 0.16; 'from:addr:cs': 0.16;
'from:addr:cskk.id.au': 0.16; 'from:name:cameron simpson': 0.16;
'hash': 0.16; 'message-id:@cskk.homeip.net': 0.16; 'object,':
0.16; 'objective': 0.16; 'received:10.10': 0.16; 'reference,':
0.16; 'removes': 0.16; 'sensible': 0.16; 'simpson': 0.16;
'wrote:': 0.16; 'problem': 0.16; 'values': 0.17; 'calls': 0.19;
'to:addr:python-list': 0.20; "i'd": 0.24; 'depends': 0.25;
'seems': 0.26; 'object': 0.26; "isn't": 0.27; 'function': 0.27;
'example,': 0.28; 'error': 0.29; 'header:User-Agent:1': 0.30;
'raise': 0.31; 'think': 0.32; 'issues.': 0.32; 'objects': 0.32;
'but': 0.32; "i'm": 0.33; 'subject:for': 0.33; 'same': 0.34;
'header:In-Reply-To:1': 0.34; 'those': 0.36; 'currently': 0.37;
'read': 0.38; 'added': 0.39; 'use': 0.39; 'me.': 0.62; 'policy':
0.62; 'simply': 0.63; 'requirement': 0.64; 'your': 0.64; 'well':
0.65; 'improve': 0.66; 'received:userid': 0.66;
'header:Received:6': 0.67; 'type:': 0.69; 'times': 0.69;
'performance': 0.71; 'little': 0.73; 'associates': 0.76;
'subsequent': 0.76; 'composed': 0.84; 'inclined': 0.84; 'say,':
0.84; 'stability': 0.84; 'sulla': 0.84; 'badly': 0.91; 'cheap':
0.91; 'dependent': 0.93; 'details,': 0.95
X-RG-Spam: Unknown
X-RazorGate-Vade: gggruggvucftvghtrhhoucdtuddrgedvvddrudeftddgudeglecutefuodetggdotefrodftvfcurfhrohhfihhlvgemucfupfevtfgpvffgnffuvffttedpqfgfvfenuceurghilhhouhhtmecugedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhepfffhvffukfggtggujggffhesthdtredttdervdenucfhrhhomhepvegrmhgvrhhonhcuufhimhhpshhonhcuoegtshestghskhhkrdhiugdrrghuqeenucggtffrrghtthgvrhhnpeevhfelhfffffeivefgieehudeutddvieffhfdvvddufefhudevtddvueegffdujeenucffohhmrghinhepghhithhhuhgsrdgtohhmpdhrvggrughmvgdrmhgunecukfhppedurdduvdelrddvgeeirdegjeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhephhgvlhhopegsohhrghdrtghskhhkrdhhohhmvghiphdrnhgvthdpihhnvghtpedurdduvdelrddvgeeirdegjedpmhgrihhlfhhrohhmpegtrghmvghrohhnsegtshhkkhdrihgurdgruhdpnhgspghrtghpthhtohepvddprhgtphhtthhopegtshestghskhhkrdhiugdrrghupdhrtghpthhtohepphihthhhohhnqdhlihhsthesphihthhhohhnrdhorhhg
X-RazorGate-Vade-Verdict: clean 0
X-RazorGate-Vade-Classification: clean
X-RG-VS-CLASS: clean
X-Authentication-Info: Submitted using ID cskk@bigpond.com
Mail-Followup-To: Python List <python-list@python.org>
Content-Disposition: inline
In-Reply-To: <CABbU2U9CwzB=ko_2n-QCG32MC3kn6R7R-m-TcOJZPPMWsULGxw@mail.gmail.com>
User-Agent: Mutt/2.2.1 (2022-02-19)
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: General discussion list for the Python programming language
<python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>,
<mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <https://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>,
<mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID: <YjEF9a4RRTjnEpBx@cskk.homeip.net>
X-Mailman-Original-References: <CABbU2U9CwzB=ko_2n-QCG32MC3kn6R7R-m-TcOJZPPMWsULGxw@mail.gmail.com>

by: Cameron Simpson - Tue, 15 Mar 2022 21:32 UTC

On 12Mar2022 21:45, Marco Sulla <Marco.Sulla.Python@gmail.com> wrote:
>I have a custom immutable object, and I added a cache for its hash
>value. The problem is the object can be composed of mutable or
>immutable objects, so the hash can raise TypeError.

Is it sensible to compute the hash only from the immutable parts?
Bearing in mind that usually you need an equality function as well and
it may have the same stability issues.

>In this case I currently cache the value -1. The subsequent calls to
>__hash__() will check if the value is -1. If so, a TypeError is
>immediately raised.

This will also make these values behave badly in dicts/sets, as they all
hash to the same bucket. The performance of a hash index is pretty
dependent on having roughly even distribution of objects amongst the
hash slots.

>The problem is the first time I get an error with details, for example:
>
>TypeError: unhashable type: 'list'
>
>The subsequent times I simply raise a generic error:
>
>TypeError

You could, you know, cache the original exception. That does keep links
to the traceback and therefore all the associates stack frames, so that
isn't cheap (it is peerfectly fast - just the reference, t just prevents
those things from being reclaimed).

>Ok, I can improve it by raising, for example, TypeError: not all
>values are hashable. But do you think this is acceptable? Now I'm
>thinking about it and it seems a little hacky to me.

That's a policy issue. "Acceptable" depends on the imagined use cases.
Im' just having a read of your intro:
https://github.com/Marco-Sulla/python-frozendict/blob/35611f4cd869383678104dc94f82aa636c20eb24/README.md

So your objective is that a frozendict can itself be hashable, allowing,
say, sets of frozendicts?

In that case I would be inclined to never raise TypeError at all. I'd
compute the hash entirely from the keys of the dict and compute equality
in the normal fashion: identical keys and then equal corresponding
values. That removes the requirement that values be immutable and/or
hashable.

It that workable?

Cheers,
Cameron Simpson <cs@cskk.id.au>

Subject	Author
Re: Best practice for caching hash	Cameron Simpson