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
>>>>
>>>
>>
>
______________________________________________
[email protected] mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel
