The hash table implementation depends on two functions: one hashes an
entry, and another compares for equality. (That's how hash collisions
are handled.) So one way to implement the more complicated fix would
follow this strategy:
Instead of inserting pointers to the strings into the hash table, insert
both a string pointer and a pointer to the entry in the `used` vector.
Use the string pointer to generate the hash, and the value pointed to by
the other part to decide if the hit is equal (i.e. it's equal if the
string pointers match and the other pointer points to `false`).
That might not be too hard...
Duncan Murdoch
On 2026-06-16 12:39 p.m., Joseph Wood wrote:> Hey Duncan,
>
> I was digging into the C code and your explanation looks right to me.
>
> One thing that initially threw me off is that pmatch is not going through
an
> integer matching path here. I first tried to reproduce the issue by
implementing
> the integer hash path and was not able to reproduce the behavior. But
pmatch
> converts both arguments to character:
>
> pmatch
> function (x, table, nomatch = NA_integer_, duplicates.ok = FALSE)
> .Internal(pmatch(as.character(x), as.character(table), nomatch,
> duplicates.ok))
>
> So the relevant case is not really
>
> c(1L, 2L, ..., 51L, 1L, 2L, ...)
>
> but
>
> c("1", "2", ..., "51", "1",
"2", ...)
>
> Looking at do_pmatch, the small input path and the hashed path seem to have
> different semantics when duplicates.ok = FALSE.
>
> The small input exact match path scans the target and skips already used
> entries:
>
> for (int j = 0; j < n_target; j++) {
> if (no_dups && used[j]) continue;
> if (strcmp(ss, tar[j]) == 0) {
> ians[i] = j + 1;
> if (no_dups) used[j] = 1;
> nexact++;
> break;
> }
> }
>
> But the hashed path asks Lookup for one representative match and then
rejects
> it if that position has already been used:
>
> int j = Lookup(target, input, i, &data);
> if ((j == 0) || (no_dups && used[j - 1])) continue;
>
> The hash table is built through DoHashing/isDuplicated, and isDuplicated
does
> not retain later equal target positions once it finds an equal existing
entry:
>
> while (h[i] != NIL) {
> if (d->equal(x, h[i], x, indx))
> return h[i] >= 0 ? 1 : 0;
> i = (i + 1) % d->M;
> }
> h[i] = (int) indx;
>
> So the hashed path can return an already used representative, even though a
> later unused duplicate exists in the table.
>
> Your explanation of the partial match pass also explains the observed
number of
> NAs. For
>
> x <- c(1:n, 1:n)
>
> the unmatched second copies then go through partial matching as strings.
Values
> like "1" are ambiguous because they partially match
"1", "10", "11", ..., "19"
> among the still unused target entries; similarly for "2" with
"20"?"29", etc.
> That lines up with seeing floor(n / 10) NAs.
>
> I agree that skipping hashing whenever duplicates.ok = FALSE would be a
much
> simpler fix, though I would expect that could be costly for large inputs
where
> the current hash path is otherwise helping.
>
> Regards,
> Joseph Wood
>
>> On 2026-06-16 7:59 a.m., Duncan Murdoch wrote:
>>> I believe the problem is that the hash code doesn't allow
values to be
>>> removed. So when x is c(1:n, 1:n) for n > 50, pmatch(x,x) gets
exact
>>> matches to the first half of the values, but not to the second
half:
>>> the hashes point to the removed values and they are rejected.
>>>
>>> When it switches to partial matches, for n=51 there are multiple
partial
>>> matches to 1:5, but not to bigger numbers, so those come out as NA.
For
>>> numbers 6:51, the partial match code sees unique partial matches
(which
>>> happen to be exact).
>>>
>>> I think the best fix is:
>>>
>>> - Fix the hash code to allow for multiple copies in the hash
table,
>>> and record whether values have been used in each of those.
>>>
>>> This would be programmed similar to handling hash collisions (which
I
>>> think aren't handled now).
>>
>> I'm wrong about that part. Hash collisions are currently not a
problem.
>> It's only the duplicates.ok=FALSE case that isn't handled
now.
>>
>> A much simpler fix is to skip hashing if duplicates.ok = FALSE. I
don't
>> know how badly that would affect performance.
>>
>> Duncan Murdoch
>>
>>>
>>>
>>> Duncan Murdoch
>>>
>>>
>>> On 2026-06-16 7:29 a.m., Peter Dalgaard wrote:
>>>> OK, so 100 is the cutoff whether to use a hash table or not. It
is still odd that it only affects a relatively short block at the beginning of
the repeated targets, though.
>>>>
>>>>> On 16 Jun 2026, at 11.54, Peter Dalgaard <pdalgd using
gmail.com> wrote:
>>>>>
>>>>> Something definitely looks odd... I certain can't think
of a reason why the behaviour would be keyed to the _size_ of the first argument
like this:
>>>>>
>>>>>> pmatch(as.character(x)[1:100], as.character(x))
>>>>> [1] 1 2 3 4 5 6 7 8 9 10 11 12 13
14 15 16 17 18
>>>>> [19] 19 20 21 22 23 24 25 26 27 28 29 30 31
32 33 34 35 36
>>>>> [37] 37 38 39 40 41 42 43 44 45 46 47 48 49
50 51 52 53 54
>>>>> [55] 55 56 57 58 59 60 61 62 63 64 65 66 67
68 69 70 71 72
>>>>> [73] 73 74 75 76 77 78 79 80 81 82 83 84 85
86 87 88 89 90
>>>>> [91] 91 92 93 94 95 96 97 98 99 100
>>>>>> pmatch(as.character(x)[1:101], as.character(x))
>>>>> [1] 1 2 3 4 5 6 7 8 9 10 11 12 13
14 15 16 17 18
>>>>> [19] 19 20 21 22 23 24 25 26 27 28 29 30 31
32 33 34 35 36
>>>>> [37] 37 38 39 40 41 42 43 44 45 46 47 48 49
50 51 NA NA NA
>>>>> [55] NA NA 57 58 59 60 61 62 63 64 65 66 67
68 69 70 71 72
>>>>> [73] 73 74 75 76 77 78 79 80 81 82 83 84 85
86 87 88 89 90
>>>>> [91] 91 92 93 94 95 96 97 98 99 100 101
>>>>>> pmatch(as.character(x)[2:102], as.character(x))
>>>>> [1] 2 3 4 5 6 7 8 9 10 11 12 13 14
15 16 17 18 19
>>>>> [19] 20 21 22 23 24 25 26 27 28 29 30 31 32
33 34 35 36 37
>>>>> [37] 38 39 40 41 42 43 44 45 46 47 48 49 50
51 1 NA NA NA
>>>>> [55] NA 57 58 59 60 61 62 63 64 65 66 67 68
69 70 71 72 73
>>>>> [73] 74 75 76 77 78 79 80 81 82 83 84 85 86
87 88 89 90 91
>>>>> [91] 92 93 94 95 96 97 98 99 100 101 102
>>>>>>> pmatch(as.character(x)[3:102], as.character(x))
>>>>> [1] 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20
>>>>> [19] 21 22 23 24 25 26 27 28 29 30 31 32 33
34 35 36 37 38
>>>>> [37] 39 40 41 42 43 44 45 46 47 48 49 50 51
1 2 54 55 56
>>>>> [55] 57 58 59 60 61 62 63 64 65 66 67 68 69
70 71 72 73 74
>>>>> [73] 75 76 77 78 79 80 81 82 83 84 85 86 87
88 89 90 91 92
>>>>> [91] 93 94 95 96 97 98 99 100 101 102
>>>>>
>>>>> It's happening in the C code, though, so some poking
around is required.
>>>>>
>>>>> - pd
>>>>>
>>>>>
>>>>>> On 15 Jun 2026, at 22.14, Duncan Murdoch
<murdoch.duncan using gmail.com> wrote:
>>>>>>
>>>>>> I think your example is overly complicated.
Wouldn't it be enough to show one vector that gives a bad result? For
example:
>>>>>>
>>>>>> x <- c(1:51, 1:51)
>>>>>> pmatch(x, x)
>>>>>>
>>>>>> which gives
>>>>>>
>>>>>> [1] 1 2 3 4 5 6 7 8 9 10 11 12 13
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
>>>>>> [30] 30 31 32 33 34 35 36 37 38 39 40 41
42 43 44 45 46 47 48 49 50 51 NA NA NA NA NA 57 58
>>>>>> [59] 59 60 61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
>>>>>> [88] 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102
>>>>>>
>>>>>> (with the NAs showing up at locations 52 to 56).
>>>>>>
>>>>>> I'm not 100% sure that's a bug, since the
documentation for pmatch doesn't discuss what should happen if table (the
second argument) contains duplicates. I think I'd agree with you that you
should get 1:102 as the output, but maybe that was never intended to be
supported.
>>>>>>
>>>>>> Duncan Murdoch
>>>>>>
>>>>>> On 2026-06-15 3:12 p.m., Fran?ois Rousset via R-devel
wrote:
>>>>>>> Dear R-devel list,
>>>>>>> the following code shows NA's appearing in the
result of pmatch() when
>>>>>>> comparing a vector to itself when the length of the
vector is more than 100.
>>>>>>> The main specificity of this example is that
elements are repeated in
>>>>>>> the vector which is matched to itself.
>>>>>>> The results when they do not include any NA (i.e.
for argument of length
>>>>>>> <=100) are exactly as I expect from the
documentation.
>>>>>>> I see that the source C code uses distinct
algorithms whether n_input <>>>>>>> 100 || n_target
<= 100 or not. Could there by a problem in the source
>>>>>>> code for larger values ?
>>>>>>> The NA's correspond to the first positions of
the second replicate of
>>>>>>> the integer sequence, e.g. positions 52 to 56 if
n=51 in the example below.
>>>>>>> But as shown below, the NA's do not appear when
the sequence is reversed
>>>>>>> before being compared to itself.
>>>>>>> This was first detected with R 4.5.3 and is
reproducible with a
>>>>>>> just-downloaded, virgin R-devel installation.
>>>>>>> Thanks in advance for any feedback,
>>>>>>> F.
>>>>>>> =====================>>>>>>>
countNAs <- function(n, rev.=FALSE) {
>>>>>>> seqn <- seq(n)
>>>>>>> if (rev.) seqn <- rev(seqn)
>>>>>>> seqn <- rep(seqn,2)
# of length 2 n: NA's
>>>>>>> appear when 2 n > 100
>>>>>>> chk <- pmatch(seqn, seqn) # I
expect the result to be
>>>>>>> seq(2*n)
>>>>>>> sum(is.na(chk))
>>>>>>> }
>>>>>>> sapply(1:100, countNAs )
>>>>>>> sapply(1:100, countNAs , rev.=TRUE)
>>>>>>> ======================>>>>>>>
Results:
>>>>>>>> sapply(1:100, countNAs )
>>>>>>> [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
>>>>>>> 0 0 0 0 0 0
>>>>>>> [29] 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
>>>>>>> 5 5 5 5 5 5
>>>>>>> [57] 5 5 5 6 6 6 6 6 6 6 6 6 6 7
7 7 7 7 7 7 7 7
>>>>>>> 7 8 8 8 8 8
>>>>>>> [85] 8 8 8 8 8 9 9 9 9 9 9 9 9 9
9 10
>>>>>>>> sapply(1:100, countNAs , rev.=TRUE)
>>>>>>> [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
>>>>>>> 0 0 0 0 0 0 0 0 0
>>>>>>> [43] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
>>>>>>> 0 0 0 0 0 0 0 0 0
>>>>>>> [85] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>>>>>>>> sessionInfo()
>>>>>>> R Under development (unstable) (2026-06-14 r90150
ucrt)
>>>>>>> Platform: x86_64-w64-mingw32/x64
>>>>>>> Running under: Windows 10 x64 (build 19045)
>>>>>>> Matrix products: default
>>>>>>> LAPACK version 3.12.1
>>>>>>> locale:
>>>>>>> [1] LC_COLLATE=French_France.utf8
LC_CTYPE=French_France.utf8
>>>>>>> [3] LC_MONETARY=French_France.utf8 LC_NUMERIC=C
>>>>>>> [5] LC_TIME=French_France.utf8
>>>>>>> time zone: Europe/Paris
>>>>>>> tzcode source: internal
>>>>>>> attached base packages:
>>>>>>> [1] stats graphics grDevices utils
datasets methods base
>>>>>>> loaded via a namespace (and not attached):
>>>>>>> [1] compiler_4.7.0 tools_4.7.0
>>>>>>> ______________________________________________
>>>>>>> R-devel using r-project.org mailing list
>>>>>>> https://stat.ethz.ch/mailman/listinfo/r-devel
>>>>>>
>>>>>> ______________________________________________
>>>>>> R-devel using r-project.org mailing list
>>>>>> https://stat.ethz.ch/mailman/listinfo/r-devel
>>>>>
>>>>> --
>>>>> Peter Dalgaard, Professor,
>>>>> Center for Statistics, Copenhagen Business School
>>>>> Solbjerg Plads 3, 2000 Frederiksberg, Denmark
>>>>> Phone: (+45)38153501
>>>>> Office: A 4.23
>>>>> Email: pd.mes using cbs.dk Priv: PDalgd using gmail.com
>>>>>
>>>>
>>>
>>