Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd74d306

Browse files
committed
Reduced allocations for pairing heap
1 parenta1b80fa commitd74d306

File tree

2 files changed

+21
-13
lines changed

2 files changed

+21
-13
lines changed

‎src/hnsw.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -162,8 +162,9 @@ struct HnswNeighborArray
162162

163163
typedefstructHnswPairingHeapNode
164164
{
165-
pairingheap_nodeph_node;
166165
HnswCandidate*inner;
166+
pairingheap_nodec_node;
167+
pairingheap_nodew_node;
167168
}HnswPairingHeapNode;
168169

169170
/* HNSW index options */

‎src/hnswutils.c‎

Lines changed: 19 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -607,16 +607,19 @@ HnswEntryCandidate(char *base, HnswElement entryPoint, Datum q, Relation index,
607607
returnhc;
608608
}
609609

610+
#defineHnswGetPairingHeapCandidate(membername,ptr) (pairingheap_container(HnswPairingHeapNode, membername, ptr)->inner)
611+
#defineHnswGetPairingHeapCandidateConst(membername,ptr) (pairingheap_const_container(HnswPairingHeapNode, membername, ptr)->inner)
612+
610613
/*
611614
* Compare candidate distances
612615
*/
613616
staticint
614617
CompareNearestCandidates(constpairingheap_node*a,constpairingheap_node*b,void*arg)
615618
{
616-
if (((constHnswPairingHeapNode*)a)->inner->distance<((constHnswPairingHeapNode*)b)->inner->distance)
619+
if (HnswGetPairingHeapCandidateConst(c_node,a)->distance<HnswGetPairingHeapCandidateConst(c_node,b)->distance)
617620
return1;
618621

619-
if (((constHnswPairingHeapNode*)a)->inner->distance>((constHnswPairingHeapNode*)b)->inner->distance)
622+
if (HnswGetPairingHeapCandidateConst(c_node,a)->distance>HnswGetPairingHeapCandidateConst(c_node,b)->distance)
620623
return-1;
621624

622625
return0;
@@ -628,10 +631,10 @@ CompareNearestCandidates(const pairingheap_node *a, const pairingheap_node *b, v
628631
staticint
629632
CompareFurthestCandidates(constpairingheap_node*a,constpairingheap_node*b,void*arg)
630633
{
631-
if (((constHnswPairingHeapNode*)a)->inner->distance<((constHnswPairingHeapNode*)b)->inner->distance)
634+
if (HnswGetPairingHeapCandidateConst(w_node,a)->distance<HnswGetPairingHeapCandidateConst(w_node,b)->distance)
632635
return-1;
633636

634-
if (((constHnswPairingHeapNode*)a)->inner->distance>((constHnswPairingHeapNode*)b)->inner->distance)
637+
if (HnswGetPairingHeapCandidateConst(w_node,a)->distance>HnswGetPairingHeapCandidateConst(w_node,b)->distance)
635638
return1;
636639

637640
return0;
@@ -746,11 +749,13 @@ HnswSearchLayer(char *base, Datum q, List *ep, int ef, int lc, Relation index, F
746749
{
747750
HnswCandidate*hc= (HnswCandidate*)lfirst(lc2);
748751
boolfound;
752+
HnswPairingHeapNode*node;
749753

750754
AddToVisited(base,&v,hc,index,&found);
751755

752-
pairingheap_add(C,&(CreatePairingHeapNode(hc)->ph_node));
753-
pairingheap_add(W,&(CreatePairingHeapNode(hc)->ph_node));
756+
node=CreatePairingHeapNode(hc);
757+
pairingheap_add(C,&node->c_node);
758+
pairingheap_add(W,&node->w_node);
754759

755760
/*
756761
* Do not count elements being deleted towards ef when vacuuming. It
@@ -764,8 +769,8 @@ HnswSearchLayer(char *base, Datum q, List *ep, int ef, int lc, Relation index, F
764769
while (!pairingheap_is_empty(C))
765770
{
766771
HnswNeighborArray*neighborhood;
767-
HnswCandidate*c=((HnswPairingHeapNode*)pairingheap_remove_first(C))->inner;
768-
HnswCandidate*f=((HnswPairingHeapNode*)pairingheap_first(W))->inner;
772+
HnswCandidate*c=HnswGetPairingHeapCandidate(c_node,pairingheap_remove_first(C));
773+
HnswCandidate*f=HnswGetPairingHeapCandidate(w_node,pairingheap_first(W));
769774
HnswElementcElement;
770775

771776
if (c->distance>f->distance)
@@ -801,7 +806,7 @@ HnswSearchLayer(char *base, Datum q, List *ep, int ef, int lc, Relation index, F
801806
HnswElementeElement=HnswPtrAccess(base,e->element);
802807
boolalwaysAdd=wlen<ef;
803808

804-
f=((HnswPairingHeapNode*)pairingheap_first(W))->inner;
809+
f=HnswGetPairingHeapCandidate(w_node,pairingheap_first(W));
805810

806811
if (index==NULL)
807812
eDistance=GetCandidateDistance(base,e,q,procinfo,collation);
@@ -811,6 +816,7 @@ HnswSearchLayer(char *base, Datum q, List *ep, int ef, int lc, Relation index, F
811816
if (eDistance<f->distance||alwaysAdd)
812817
{
813818
HnswCandidate*ec;
819+
HnswPairingHeapNode*node;
814820

815821
Assert(!eElement->deleted);
816822

@@ -823,8 +829,9 @@ HnswSearchLayer(char *base, Datum q, List *ep, int ef, int lc, Relation index, F
823829
HnswPtrStore(base,ec->element,eElement);
824830
ec->distance=eDistance;
825831

826-
pairingheap_add(C,&(CreatePairingHeapNode(ec)->ph_node));
827-
pairingheap_add(W,&(CreatePairingHeapNode(ec)->ph_node));
832+
node=CreatePairingHeapNode(ec);
833+
pairingheap_add(C,&node->c_node);
834+
pairingheap_add(W,&node->w_node);
828835

829836
/*
830837
* Do not count elements being deleted towards ef when
@@ -847,7 +854,7 @@ HnswSearchLayer(char *base, Datum q, List *ep, int ef, int lc, Relation index, F
847854
/* Add each element of W to w */
848855
while (!pairingheap_is_empty(W))
849856
{
850-
HnswCandidate*hc=((HnswPairingHeapNode*)pairingheap_remove_first(W))->inner;
857+
HnswCandidate*hc=HnswGetPairingHeapCandidate(w_node,pairingheap_remove_first(W));
851858

852859
w=lappend(w,hc);
853860
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp