[ https://issues.apache.org/jira/browse/MAHOUT-1890?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15596137#comment-15596137 ]
Andrew Musselman commented on MAHOUT-1890: ------------------------------------------ Thanks anyway Michael :) > 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)