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
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

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
584–588

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.

3280

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
584–588

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 32453

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!(