You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by "Michael M. (JIRA)" <ji...@apache.org> on 2016/10/21 19:31:58 UTC
[jira] [Resolved] (MAHOUT-1890) Infinite loop in
OpenLongObjectHashMap
[ https://issues.apache.org/jira/browse/MAHOUT-1890?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Michael M. resolved MAHOUT-1890.
--------------------------------
Resolution: Duplicate
> Infinite 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 an infinite 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)