[ 
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)

Reply via email to