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