Opened 3 years ago

Closed 3 years ago

#26776 closed enhancement (fixed)

MonoDict/TripleDict: optimize use of KeyedRef

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-8.5
Component: coercion Keywords:
Cc: SimonKing Merged in:
Authors: Jeroen Demeyer Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: c9631a7 (Commits, GitHub, GitLab) Commit: c9631a7b47cabf98fc4e992defef27dc9e587953
Dependencies: Stopgaps:

Status badges

Description (last modified by jdemeyer)

Some useful micro-optimizations can be done to MonoDict and TripleDict:

  1. Replace isinstance(x, KeyedRef) by type(x) is KeyedRef.
  1. In __getitem__ and __contains__, do not check whether the KeyedRef for the key is dead: we are passed a reference to it as argument, so it must be alive.
  1. Replace PyWeakref_GetObject by PyWeakref_GET_OBJECT.
  1. Optimize the hash used in lookup() by throwing away useless low-order bits.

We also add an inline function is_dead_keyedref for isinstance(x, KeyedRef) and PyWeakref_GetObject(x) is Py_None to simplify some code.

Change History (14)

comment:1 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 3 years ago by jdemeyer

  • Branch set to u/jdemeyer/monodict_tripledict__optimize_use_of_keyedref

comment:3 Changed 3 years ago by jdemeyer

  • Commit set to 1f0ff36385312c66eed947821f44968ce6b0c566
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

​1f0ff36Micro-optimizations in MonoDict/TripleDict

comment:4 Changed 3 years ago by jdemeyer

  • Cc SimonKing added

comment:5 Changed 3 years ago by jdemeyer

Reviewing some of this code makes me wonder whether we really need all those checks for dead KeyedRefs in get(). Shouldn't the eraser ensure that no dead references occur?

comment:6 Changed 3 years ago by jdemeyer

In more detail: if we find a dead weakref in __getitem__ (or __contains__ which is similar), lookup() guarantees that the id() of the key in the dict matches the given key. If it's really the same key, then the weakref should not be dead since we have a live reference (passed as argument to __getitem__). If it's not the same key, then it must be a recycled id(). But that can only happen once the original key has been freed from memory, which happens after the weakref callback, which should remove the entry from the dict.

So I don't see any scenario how a dead weakref could be found in __getitem__, but I might be missing something...

comment:7 Changed 3 years ago by jdemeyer

(Note: the reasoning above is for dead keys; dead values could still occur in the middle of a deallocation)

comment:8 Changed 3 years ago by git

  • Commit changed from 1f0ff36385312c66eed947821f44968ce6b0c566 to f49d18fd0673b4df1b29a310871fce7ad12a629b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​f49d18fMicro-optimizations in MonoDict/TripleDict

comment:9 Changed 3 years ago by git

  • Commit changed from f49d18fd0673b4df1b29a310871fce7ad12a629b to e09f5d8b657579a9fb756e9438bc0aa60dd3c5d6

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​e09f5d8Micro-optimizations in MonoDict/TripleDict

comment:10 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:11 Changed 3 years ago by git

  • Commit changed from e09f5d8b657579a9fb756e9438bc0aa60dd3c5d6 to acdfce1e75f8f3f58ab60cb2f6e6d40b9713ba03

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​acdfce1Micro-optimizations in MonoDict/TripleDict

comment:12 Changed 3 years ago by git

  • Commit changed from acdfce1e75f8f3f58ab60cb2f6e6d40b9713ba03 to c9631a7b47cabf98fc4e992defef27dc9e587953

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​c9631a7Micro-optimizations in MonoDict/TripleDict

comment:13 Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:14 Changed 3 years ago by vbraun

  • Branch changed from u/jdemeyer/monodict_tripledict__optimize_use_of_keyedref to c9631a7b47cabf98fc4e992defef27dc9e587953
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.