Michael M. created MAHOUT-1890:
----------------------------------
Summary: Tight loop in OpenLongObjectHashMap
Key: MAHOUT-1890
URL: https://issues.apache.org/jira/browse/MAHOUT-1890
Project: Mahout
Issue Type: Bug
Components: collections
Affects Versions: 1.0.0
Environment: java version "1.8.0_66"
Java(TM) SE Runtime Environment (build 1.8.0_66-b17)
Java HotSpot(TM) 64-Bit Server VM (build 25.66-b17, mixed mode)
Reporter: Michael M.
It seems that OpenLongObjectHashMap<>
(org.apache.mahout:mahout-collections:1.0) can enter a state where containsKey
(indexOfKey) ends up in a tight loop, stuck in this loop:
{code:title=OpenLongObjectHashMap.java|borderStyle=solid}
while (state[i] != FREE && (state[i] == REMOVED || table[i] != key)) {
i -= decrement;
//hashCollisions++;
if (i < 0) {
i += length;
}
}
{code}
I haven't identified a minimum set of operations necessary to reach this state,
but I have generated a (fairly large) test that achieves it:
{code:title=TestOpenLongObjectHashMap.java|borderStyle=solid}
import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;
import org.apache.mahout.math.map.OpenLongObjectHashMap;
import org.junit.Test;
public class TestOpenLongObjectHashMap {
private static final List<Consumer<OpenLongObjectHashMap<Long>>> transcript
=
Arrays.asList(add(66546), add(66847), add(71319), del(71319),
add(80177), del(80177), add(88428),
add(88861), add(92709), del(92709), add(94392),
del(94392), add(99506), del(99506),
add(104232), add(104968), del(104232), del(104968),
add(111042), del(111042), add(123271),
del(123271), add(130887), del(66847), add(131387),
add(131537), add(131569), del(131537),
add(135253), del(135253), add(138781), del(138781),
add(141689), del(141689), add(144224),
del(144224), add(147237), del(147237), add(152945),
add(153646), del(152945), add(154915),
del(154915), add(155621), del(155621), add(158464),
add(158724), del(158724), del(158464),
add(174017), del(174017), add(176818), del(176818),
add(178344), add(178716), del(178344),
add(178956), del(178956), del(178716), add(181714),
del(181714), add(188533), del(188533),
add(189152), del(189152), del(131569), add(193603),
add(193614), add(193632), del(193614),
add(193650), add(193661), add(193662), del(193662),
add(193691), add(193761), del(193661),
del(193761), add(193801), add(193812), del(193650),
del(131387), del(193603), add(193837),
del(193837), add(194160), add(194175), del(194160),
add(194224), del(194175), add(195507),
add(195617), add(195838), add(196272), add(196402),
add(196410), del(196272), del(195507),
add(196426), add(196427), del(193691), add(196439),
add(196440), del(195838), add(196449),
del(196426), add(196460), add(196634), del(196449),
del(196402), del(196439), del(196440),
add(197250), add(197482), add(197531), del(193632),
add(197983), del(197250), del(197983),
del(196634), add(199455), add(199648), add(200356),
add(200397), add(200711), del(200356),
del(199648), add(201133), del(200711), add(201209),
del(201209), del(196410), del(200397),
add(205160), del(205160), del(197531), del(196427),
add(207533), add(207546), del(196460),
del(197482), add(207555), add(207556), add(207660),
add(207820), del(207555), del(207556),
del(207660), add(208887), add(208944), del(208944),
add(210976), del(210976), add(212301),
del(208887), add(213198), del(207546), del(213198),
add(213321), del(212301), add(213402),
add(214597), del(214597), add(224378), add(225915),
add(229080), del(213402), add(229346),
del(225915), del(224378), add(231030), add(231151),
add(231373), del(231030), del(231373),
del(229080), add(232821), del(232821), add(233121),
add(233146), del(233146), del(233121),
add(233947), del(233947), del(229346), add(234011),
add(234078), add(234093), del(207820),
add(234582), del(207533), add(234590), add(235295),
add(235463), add(235815), del(235295),
del(234582), del(235815), add(236133), del(236133),
del(235463), add(239925), add(239957),
del(239957), add(242934), del(242934), add(243629),
add(244092), del(234078), del(243629),
del(234011), add(244298), add(244413), add(244427),
add(244695), del(244092), del(244695),
add(245241), del(239925), del(234093), add(247267),
del(244298), del(231151), add(247766),
add(247772), add(247773), add(247892), del(244413),
add(249689), add(249831), del(249831),
del(245241), add(253283), del(249689), del(253283),
add(254814), del(254814), add(256746),
add(258382), del(244427), add(259392), del(256746),
del(258382), add(263266), add(266622),
add(267835), del(267835), del(266622), add(270727),
add(270786), add(271043), del(271043),
del(270727), add(274128), del(274128), del(270786),
add(276954), del(276954), add(277773),
add(277827), del(277773), add(278443), del(278443),
del(277827), add(280444), add(280476),
add(286186), add(286193), del(286186), add(286205),
del(234590), del(201133), del(247267),
add(286322), add(286330), del(263266), del(199455),
del(286205), add(286376), add(286378),
del(280476), del(259392), add(286434), add(286539),
add(288067), add(290067), del(290067),
add(290809), del(290809), del(288067), add(295950),
del(280444), add(296556), add(297276),
del(296556), add(297704), add(297907), add(297936),
add(297947), add(297956), del(286539),
del(297936), add(298595), add(298616), add(298617),
add(298643), del(297947), add(298700),
add(298701), add(299170), del(299170), del(295950),
del(297276), del(286322), add(299644),
add(299750), del(286378), add(299751), del(286434),
add(299900), add(300040), del(300040),
add(300165), del(299900), add(302324), del(302324),
add(304371), del(304371), add(306117),
del(306117), add(306751), add(307193), del(306751),
del(307193), add(307561), del(299644),
add(307848), add(307894), del(307894), del(307848),
add(308326), del(307561), del(308326),
add(311198), del(311198), add(314100), add(314250),
add(314454), add(315195), add(315750),
add(317668), add(318585), add(319988), add(320038),
add(320634), del(320634), add(321154),
add(322377), add(322405), del(322405), del(321154),
add(322989), add(323488), add(323489),
del(323488), del(322989), add(324668), del(323489),
add(325651), add(325675), del(325651),
add(326387), add(326654), del(326387), del(326654),
del(325675), add(327454), add(327844),
add(327888), add(328541), del(327844), del(324668),
add(329002), add(329792), del(329792),
del(329002), add(331123), del(328541), del(331123),
add(331626), add(333869), del(333869),
add(333939), add(333940), del(333940), del(333939),
add(334532), del(334532), del(298616),
del(298617), add(336577), add(336578), add(336723),
del(317668), add(337556), add(337557),
del(336723), add(338153), del(338153), add(339818),
add(340153), del(340153), del(339818),
add(340253), del(340253), add(341507), del(322377),
add(342285), del(341507), del(331626),
add(343334), del(300165), add(343339), del(343339),
del(343334), add(343453), add(343515),
del(343515), add(343958), del(343958), del(195617),
add(345163), add(346229), del(346229),
del(345163), add(348094), add(348581), add(348958),
del(343453), del(348958), del(348581),
add(349217), add(349218), del(349218), del(349217),
del(342285), add(350002), add(350833),
del(350833), add(352160), del(352160), add(354943),
del(354943), add(359170), add(359465),
add(359480), del(359465), del(359480), del(350002),
del(359170), add(363634), del(363634),
add(364606), add(367965), del(367965), add(369082),
del(369082), del(364606), add(370023),
del(370023), add(371449), add(371450), del(371450),
del(371449), add(371526), del(371526),
add(371834), add(371928), del(371834), del(371928),
add(372151), add(372228), add(372276),
del(372276), del(372228), add(372364), add(372601),
add(372602), del(372151), del(372364),
del(372602), add(373037), add(373046), del(373037),
add(373288), del(373288), del(373046),
del(337557), add(375867), add(376358), add(376582),
del(376582), add(378272), del(378272),
add(380800), add(381955), add(381958), del(381958),
del(372601), add(382278));
public static Consumer<OpenLongObjectHashMap<Long>> add(final long id) {
return (map) -> map.put(id, id);
}
public static Consumer<OpenLongObjectHashMap<Long>> del(final long id) {
return (map) -> map.removeKey(id);
}
@Test
public void spinsForever() {
final OpenLongObjectHashMap<Long> map = new OpenLongObjectHashMap<>();
for (final Consumer<OpenLongObjectHashMap<Long>> consumer : transcript)
{
consumer.accept(map);
}
map.clear();
map.put(254, 254L);
map.put(2829, 2829L);
// We get this far, containsKey ends up spinning in
OpenLongObjectHashMap::indexOfKey
map.containsKey(2866);
}
}
{code}
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
