( )⚙ D12209 revlog: implement fast_rank retrieval in C

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D12209

revlog: implement fast_rank retrieval in C
ClosedPublic

Authored by pacien on Feb 21 2022, 12:13 PM.

Details

Reviewers
indygreg
Alphare
Group Reviewers
hg-reviewers
Commits
rHGe633e660158f: revlog: implement fast_rank retrieval in C
Summary

This will be useful in particular to avoid going through the Python interpreter
in native Rust functions.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

pacien created this revision.Feb 21 2022, 12:13 PM
indygreg requested changes to this revision.Mar 1 2022, 8:04 PM
indygreg added a subscriber: indygreg.
indygreg added inline comments.
mercurial/cext/revlog.c
596–600

I _think_ our clang-format policy requires braces around if. I could be wrong. But, I personally prefer we always use if { to avoid bugs.

3298

This version (and its reference in the Python code I believe) needs to be incremented to 3 since a field was added to Revlog_CAPI.

This revision now requires changes to proceed.Mar 1 2022, 8:04 PM
Alphare added a subscriber: Alphare.Mar 2 2022, 4:32 AM
Alphare added inline comments.
mercurial/cext/revlog.c
596–600

It does not, but I agree that this is easily prone to bugs.

pacien updated this revision to Diff 32392.Mar 2 2022, 1:16 PM
pacien marked 3 inline comments as done.Mar 2 2022, 1:17 PM

Amended.

Alphare accepted this revision.Mar 3 2022, 6:02 AM
pacien added a commit: rHGe633e660158f: revlog: implement fast_rank retrieval in C.Mar 3 2022, 6:07 AM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGe633e660158f: revlog: implement fast_rank retrieval in C (authored by pacien). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/revlog.c (34 lines)
Mrust/hg-cpython/src/cindex.rs (6 lines)

Diff 32392

mercurial/cext/revlog.c

typedef struct { typedef struct {
int children[16]; int children[16];
} nodetreenode; } nodetreenode;
typedef struct { typedef struct {
int abi_version; int abi_version;
Py_ssize_t (*index_length)(const indexObject *); Py_ssize_t (*index_length)(const indexObject *);
const char *(*index_node)(indexObject *, Py_ssize_t); const char *(*index_node)(indexObject *, Py_ssize_t);
int (*fast_rank)(indexObject *, Py_ssize_t);
int (*index_parents)(PyObject *, int, int *); int (*index_parents)(PyObject *, int, int *);
} Revlog_CAPI; } Revlog_CAPI;
/* /*
* A base-16 trie for fast node->rev mapping. * A base-16 trie for fast node->rev mapping.
* *
* Positive value is index of the next node in the trie * Positive value is index of the next node in the trie
* Negative value is a leaf: -(rev + 2) * Negative value is a leaf: -(rev + 2)
raise_revlog_error(); raise_revlog_error();
return NULL; return NULL;
} }
return data ? node_id : NULL; return data ? node_id : NULL;
} }
/* /*
* Return the stored rank of a given revision if known, or rank_unknown
* otherwise.
*
* The rank of a revision is the size of the sub-graph it defines as a head.
* Equivalently, the rank of a revision `r` is the size of the set
* `ancestors(r)`, `r` included.
*
* This method returns the rank retrieved from the revlog in constant time. It
* makes no attempt at computing unknown values for versions of the revlog
* which do not persist the rank.
*/
static int index_fast_rank(indexObject *self, Py_ssize_t pos)
{
Py_ssize_t length = index_length(self);
int rank;
if (self->format_version != format_cl2 || pos >= length) {
return rank_unknown;
}
if (pos == nullrev) {
indygregUnsubmitted
Done

I _think_ our clang-format policy requires braces around if. I could be wrong. But, I personally prefer we always use if { to avoid bugs.

indygreg: I _think_ our clang-format policy requires braces around `if`. I could be wrong. But, I…
AlphareUnsubmitted
Done

It does not, but I agree that this is easily prone to bugs.

Alphare: It does not, but I agree that this is easily prone to bugs.
return 0; /* convention */
}
return *(index_deref(self, pos) + entry_cl2_offset_rank);
}
/*
* Return the hash of the node corresponding to the given rev. The * Return the hash of the node corresponding to the given rev. The
* rev is assumed to be existing. If not, an exception is set. * rev is assumed to be existing. If not, an exception is set.
*/ */
static const char *index_node_existing(indexObject *self, Py_ssize_t pos) static const char *index_node_existing(indexObject *self, Py_ssize_t pos)
{ {
const char *node = index_node(self, pos); const char *node = index_node(self, pos);
if (node == NULL) { if (node == NULL) {
PyErr_Format(PyExc_IndexError, "could not access rev %d", PyErr_Format(PyExc_IndexError, "could not access rev %d",
Py_XDECREF(idx); Py_XDECREF(idx);
Py_XDECREF(cache); Py_XDECREF(cache);
return NULL; return NULL;
} }
static Revlog_CAPI CAPI = { static Revlog_CAPI CAPI = {
/* increment the abi_version field upon each change in the Revlog_CAPI /* increment the abi_version field upon each change in the Revlog_CAPI
struct or in the ABI of the listed functions */ struct or in the ABI of the listed functions */
2, 3, index_length, index_node, index_fast_rank, HgRevlogIndex_GetParents,
indygregUnsubmitted
Done

This version (and its reference in the Python code I believe) needs to be incremented to 3 since a field was added to Revlog_CAPI.

indygreg: This version (and its reference in the Python code I believe) needs to be incremented to `3`…
index_length,
index_node,
HgRevlogIndex_GetParents,
}; };
void revlog_module_init(PyObject *mod) void revlog_module_init(PyObject *mod)
{ {
PyObject *caps = NULL; PyObject *caps = NULL;
HgRevlogIndex_Type.tp_new = PyType_GenericNew; HgRevlogIndex_Type.tp_new = PyType_GenericNew;
if (PyType_Ready(&HgRevlogIndex_Type) < 0) if (PyType_Ready(&HgRevlogIndex_Type) < 0)
return; return;

rust/hg-cpython/src/cindex.rs

use cpython::{ use cpython::{
exc::ImportError, exc::TypeError, ObjectProtocol, PyClone, PyErr, exc::ImportError, exc::TypeError, ObjectProtocol, PyClone, PyErr,
PyObject, PyResult, PyTuple, Python, PythonObject, PyObject, PyResult, PyTuple, Python, PythonObject,
}; };
use hg::revlog::{Node, RevlogIndex}; use hg::revlog::{Node, RevlogIndex};
use hg::{Graph, GraphError, Revision, WORKING_DIRECTORY_REVISION}; use hg::{Graph, GraphError, Revision, WORKING_DIRECTORY_REVISION};
use libc::{c_int, ssize_t}; use libc::{c_int, ssize_t};
const REVLOG_CABI_VERSION: c_int = 2; const REVLOG_CABI_VERSION: c_int = 3;
#[repr(C)] #[repr(C)]
pub struct Revlog_CAPI { pub struct Revlog_CAPI {
abi_version: c_int, abi_version: c_int,
index_length: index_length:
unsafe extern "C" fn(index: *mut revlog_capi::RawPyObject) -> ssize_t, unsafe extern "C" fn(index: *mut revlog_capi::RawPyObject) -> ssize_t,
index_node: unsafe extern "C" fn( index_node: unsafe extern "C" fn(
index: *mut revlog_capi::RawPyObject, index: *mut revlog_capi::RawPyObject,
rev: ssize_t, rev: ssize_t,
) -> *const Node, ) -> *const Node,
fast_rank: unsafe extern "C" fn(
index: *mut revlog_capi::RawPyObject,
rev: ssize_t,
) -> ssize_t,
index_parents: unsafe extern "C" fn( index_parents: unsafe extern "C" fn(
index: *mut revlog_capi::RawPyObject, index: *mut revlog_capi::RawPyObject,
rev: c_int, rev: c_int,
ps: *mut [c_int; 2], ps: *mut [c_int; 2],
) -> c_int, ) -> c_int,
} }
py_capsule!( py_capsule!(