[rules-dev] Lazily Enabled Truth Maintenace (Project Propsoal)
Mark Proctor
mproctor at codehaus.org
Fri Sep 24 18:54:21 EDT 2010
Work looks good, I've applied the patch.
https://jira.jboss.org/browse/JBRULES-2709
Mark
On 24/09/2010 23:28, Mark Proctor wrote:
> On 23/09/2010 13:44, Leonardo Gomes wrote:
>> Hi,
>>
>> I implemented the test cases you suggested, Mark, and started working
>> on the counter. I discussed a bit with Edson yesterday and he
>> clarified the difference between the counter for logically inserted
>> facts and the fact id counter. This part seems to be fine, but I have
>> a problem with the following scenario:
>>
>> After an initial activation of TMS I put everything in the equality
>> map, then, due to retractions, the counter gets back to zero and I
>> have to disable TMS for that specific type. When a new fact is
>> logically inserted I have to look at the OTN memory and get
>> everything that was inserted there since the last deactivation of
>> TMS, to be be able to re-enable it. To do so I use the fact handle id
>> that I'm supposed to have stored together with the counter. Fine.
>>
>> *Problem: *Since the OTN memory is an ObjectHashSet, I will have to
>> iterate through it and filter (there's an ObjectFilter interface that
>> I think I can implement) all the elements that have id greater than
>> the one I stored. This will probably be inefficient and still likely
>> to cause churn.
>>
>> *Possible solutions:*
>>
>> 1) Use a TreeMap? ** Don't think so, HashSet retrieval and insertion
>> is O(1), on average, whereas TreeMap is O(log(n));
>>
>> 2) Use a LinkedHashSet (probably a homegrown implementation on top of
>> ObjectHashSet)? ** Would allow me to get the ObjectEntry I want and
>> then call getNext() up to the end, inserting all of them in the
>> equality map;
>>
>> 3) Never disable TMS for a given type once it has been enabled? ** I
>> think that lazily enabling TMS per type might be already enough an
>> optimization, in a sense that the overhead with the calculation of
>> the delta and all this logic to disable/re-enable might not be
>> worthy. Moreover, switching from HashSet to LinkedHashSet may have
>> some disadvantages.
> Lets get it working with just lazy enabling to begin with, so for now
> it can't be disabled once enabled. Once that is working we can look
> into how we can make it disable and decide if it's worth doing or not.
>
> Mark
>>
>> What do you think?
>>
>> Cheers,
>> Leo.
>>
>>
>> On Tue, Sep 21, 2010 at 12:09 AM, Mark Proctor <mproctor at codehaus.org
>> <mailto:mproctor at codehaus.org>> wrote:
>>
>> On 20/09/2010 21:58, Leonardo Gomes wrote:
>>> Ok, it took me much longer that I had thought, but I think it's
>>> working now.. all tests passing except for
>>> ReteooWorkingMemoryTest that does:
>>>
>>> FactHandle fd = workingMemory.insert( string );
>>>
>>> assertEquals( 1,
>>> tms.getAssertMap().size() );
>>>
>>>
>>> Which is a good sign, since tms is now empty as long as you
>>> haven't done any logical insert :)
>>>
>>> I implemented just the first part of your suggestion, with a
>>> boolean. I will try to implement the solution with the counter
>>> later this week and maybe do some adjustments before submitting
>>> a patch.
>>>
>>> Do you have any suggestion in terms of unit tests that you would
>>> like to see or just the apparent lack of regressions is enough?
>>> Well, I can also think of some tests by taking
>>> ReteooWorkingMemoryTest as an example, in case you don't have
>>> anything particular in mind.
>> When you do some insertions cast to get some of the internal data
>> structures and check the equality map is null, maybe check the OT
>> confs are false, do a logical insertion check it can turn on for
>> specific OTNs and not all and that it correctly adds all objects
>> for the OTN. This will be important for the next stage of the work.
>>
>> Mark
>>
>>>
>>> Cheers,
>>> Leo.
>>>
>>>
>>>
>>>
>>> On Mon, Sep 20, 2010 at 5:14 PM, Mark Proctor
>>> <mproctor at codehaus.org <mailto:mproctor at codehaus.org>> wrote:
>>>
>>> On 20/09/2010 15:53, Leonardo Gomes wrote:
>>>> I think I wasn't quite clear in my last email, so let me
>>>> try to reformulate it:
>>>>
>>>> I also gave it a try to try to do what you suggested here
>>>> (http://blog.athico.com/2010/09/lazily-enabled-truth-maintenace.html),
>>>> Mark, and couldn't make it work due to the following
>>>> situation:
>>>>
>>>> 1) Current code seems to rely on the equality map to know
>>>> that a logical insert (insertLogical) for an object that
>>>> has already been regularly inserted (insert) should be ignored;
>>> You would need to lazily maintain an equality map. When the
>>> first logical insertion is done we will have to first
>>> populate that map from the Object Type Node set of FactHandles.
>>> In the "insert" one of the first lines is:
>>> ObjectTypeConf typeConf =
>>> this.typeConfReg.getObjectTypeConf( this.entryPoint,
>>>
>>> object );
>>>
>>> So we get the ObjectTypeConf before we do anything with the
>>> object itself, and we can check if TMS is being maintained
>>> for that Object Type.
>>>
>>>>
>>>> 2) If I apply the modifications that you suggested, from
>>>> what I understood, things would start to be put in the
>>>> equality map only when a logical insert is issued;
>>>>
>>>> *Problem*: How would I handle the situation described in
>>>> item 1, if I don't have anything in the equality map at the
>>>> moment a logical insert comes in and I have to "lazily
>>>> activate" TMS?
>>> final Rete source = this.ruleBase.getRete();
>>> ClassObjectType cot = new ClassObjectType( MyClass.class );
>>> Map<ObjectType, ObjectTypeNode> map =
>>> source.getObjectTypeNodes( EntryPoint.DEFAULT );
>>> ObjectTypeNode node = map.get( cot );
>>> final ObjectHashSet memory = (ObjectHashSet)
>>> workingMemory.getNodeMemory( node );
>>>
>>> That "memory" is the set of currently asserted objects for
>>> that OTN. You can now iterate that and populate the equality
>>> hash map. This is a one off as the flag will be set on the
>>> ObjectTypeConf from then on and all objects will be added to
>>> the equality map at the point of insertion.
>>>
>>> Does that help? All the information is there, you should
>>> have to know how to retrieve it :) We don't currently
>>> maintain TMS for anything other than the default entry
>>> point. Although I think that was a mistake and we will
>>> probably move all entrypoints to work with same, but for now
>>> you can ignore that and just focus on the default.
>>>
>>> Btw this should not be confused with "equality" mode where
>>> the equality map has to be maintained by default from the
>>> start. Some would argue that a rule engine should only under
>>> work and understand on the bases of equality and thus all
>>> users must implement hashcode and equals correctly...
>>>>
>>>> --
>>>>
>>>> Moreover, I'm willing to attempt to implement the left and
>>>> right un-linking and tried to start with this easier task
>>>> to start to get familiar with drools-core. I already read
>>>> the article you linked and your article. Would you have any
>>>> document with an overview of the way drools implements rete?
>>> not really no, Rete has already well documented in a number
>>> of papers. The best thing to do is get onto irc and talk
>>> directly to edson and I and we can walk you through classes.
>>> http://www.jboss.org/drools/irc.html
>>>
>>> Mark
>>>
>>>>
>>>> Thanks in advance!
>>>>
>>>> Cheers,
>>>> Leo.
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> On Sat, Sep 18, 2010 at 3:49 AM, Leonardo Gomes
>>>> <leonardo.f.gomes at gmail.com
>>>> <mailto:leonardo.f.gomes at gmail.com>> wrote:
>>>>
>>>> if you look at the AbstractWorkingMemory insert
>>>> method you'll see one argument is whether it's a
>>>> logical insertion or not. You'll also see it check
>>>> the global maintainTMS configuration and also
>>>> retrieve the ObjectTypeConf. So between those
>>>> things someone should be able to get it working.
>>>>
>>>>
>>>> Today, it enters a block where it operates on the
>>>> equality map and also creates a default handle based on
>>>> that TMS global option and *regardless* of whether it's
>>>> a logical insert.
>>>>
>>>> If I'm *not* putting things in the equality map for
>>>> regular inserts, when a logical insert comes in, but
>>>> there were already stated inserts, how will I know
>>>> that? I would create a new handle for the logical
>>>> insert and do the tms.addLogicalDependency(...), even
>>>> tough there were regular inserts before and this seems
>>>> to be a wrong behaviour.
>>>>
>>>> Apparently, today, you can disable TMS and still use
>>>> logical inserts in your drl, what, I believe, will lead
>>>> to inconsistent behaviour, but you're at your own risk.
>>>>
>>>> Ideas? I feel that I missed something :)
>>>>
>>>> Cheers,
>>>> Leo.
>>>>
>>>> P.S.: I reached the conclusions above based on the fact
>>>> that LogicalAssertionTest started failing after I did
>>>> the changes you suggested.
>>>>
>>>>
>>>>
>>>>
>>>> On Wed, Sep 15, 2010 at 3:47 PM, Mark Proctor
>>>> <mproctor at codehaus.org <mailto:mproctor at codehaus.org>>
>>>> wrote:
>>>>
>>>> On 15/09/2010 14:35, Michael Anstis wrote:
>>>>> Is this in drools-core; or drools-compiler?
>>>>>
>>>>> Whilst not undertaking to do the work; have a
>>>>> purpose to nose through the code makes
>>>>> understanding easier.
>>>> It's all in DroolsCore.
>>>>
>>>> It's a 5 minute hack for me and then 15 minute unit
>>>> writing test. But I thought I'd write it up in a
>>>> hope to bring someone else into the fold, we need
>>>> more help writting the core engine someone else out
>>>> there must want to work on current edge engine
>>>> design :)
>>>>
>>>> if you look at the AbstractWorkingMemory insert
>>>> method you'll see one argument is whether it's a
>>>> logical insertion or not. You'll also see it check
>>>> the global maintainTMS configuration and also
>>>> retrieve the ObjectTypeConf. So between those
>>>> things someone should be able to get it working.
>>>>
>>>> Mark
>>>>
>>>>>
>>>>> On 14 September 2010 16:47, Mark Proctor
>>>>> <mproctor at codehaus.org
>>>>> <mailto:mproctor at codehaus.org>> wrote:
>>>>>
>>>>> Here is another project proposal, this time
>>>>> simpler. I think this one has Wolfgang's name
>>>>> on it ;)
>>>>>
>>>>> http://blog.athico.com/2010/09/lazily-enabled-truth-maintenace.html
>>>>>
>>>>> Three weeks ago I posted the project idea for
>>>>> "Left and Right Unlinking"
>>>>> <http://blog.athico.com/2010/08/left-and-right-unlinking-community.html>.
>>>>> So far there are no takers, so if you are
>>>>> interested let me know :)
>>>>>
>>>>> In the meantime I tried to think of a simpler
>>>>> enhancement that we would like to see done.
>>>>>
>>>>> At the moment Drools has a user setting
>>>>> "MaintainTMSOption" which can be true or
>>>>> false. It's a small optimisation that when
>>>>> turned off avoids using the equality hashmap
>>>>> that is maintained for all inserted objects.
>>>>>
>>>>> It would be a much better idea to remove this
>>>>> configuration setting, thus simplifying things
>>>>> for end users and have TMS lazily enabled on
>>>>> demand.
>>>>>
>>>>> For each object type there is an
>>>>> "ObjectTypeConf" configuration object that is
>>>>> retrieved every time a working memory action,
>>>>> such as insert, is executed. The enabledTMS
>>>>> boolean should be moved there, so there is one
>>>>> per object type, by default it is false.
>>>>>
>>>>> When a working memory action occurs, like
>>>>> insert, it retrieved the ObjectTypeConf and
>>>>> checks the maintainTms boolean there, instead
>>>>> of the current engine scoped configuration.
>>>>> When a logical insertion occurs and the
>>>>> ObjectTypeConf is retrieved if maintainTms is
>>>>> false it sets the value to true and then
>>>>> iterates the associated ObjectTypeNode memory
>>>>> lazily adding all the objects to the TMS
>>>>> equality map. From then on for that ObjectType
>>>>> all inserted objects are added to that
>>>>> equality map.
>>>>>
>>>>> With this you now have the advantage of TMS
>>>>> being laziy enabled, so the minor hashmap
>>>>> operation is no longer used and likewise a
>>>>> small memory saving from not populating the
>>>>> map. There is a further advantage that this is
>>>>> now fine grained and when enabled only impacts
>>>>> for that specific object type.
>>>>>
>>>>> A further enhancement could use a int counter,
>>>>> instead of a boolean. Each logical insertion
>>>>> for that object type increases the counter,
>>>>> each retraction decreases the counter; even if
>>>>> automatically retracted if the truth is broken
>>>>> for that logical assertion. When the counter
>>>>> reaches zero, TMS for that OTN can be
>>>>> disabled. We do not however remove the objects
>>>>> from the equality map, as this would cause
>>>>> "churn" if TMS is continuously enabled and
>>>>> disabled. Instead when TMS is disabled record
>>>>> the current fact counter id. Then if TMS is
>>>>> disabled on a retraction but there is a
>>>>> counter id, we can check that counter id to
>>>>> see if the fact is prior to TMS being disabled
>>>>> and thus would need to be retracted from the
>>>>> equality map.
>>>>>
>>>>> _______________________________________________
>>>>> rules-dev mailing list
>>>>> rules-dev at lists.jboss.org
>>>>> <mailto:rules-dev at lists.jboss.org>
>>>>> https://lists.jboss.org/mailman/listinfo/rules-dev
>>>>>
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> rules-dev mailing list
>>>>> rules-dev at lists.jboss.org <mailto:rules-dev at lists.jboss.org>
>>>>> https://lists.jboss.org/mailman/listinfo/rules-dev
>>>>
>>>>
>>>> _______________________________________________
>>>> rules-dev mailing list
>>>> rules-dev at lists.jboss.org
>>>> <mailto:rules-dev at lists.jboss.org>
>>>> https://lists.jboss.org/mailman/listinfo/rules-dev
>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>
>
> _______________________________________________
> rules-dev mailing list
> rules-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-dev/attachments/20100924/7815a86b/attachment-0001.html
More information about the rules-dev
mailing list