[rules-dev] Lazily Enabled Truth Maintenace (Project Propsoal)
Mark Proctor
mproctor at codehaus.org
Tue Oct 5 22:07:03 EDT 2010
On 24/09/2010 23:54, Mark Proctor wrote:
> Work looks good, I've applied the patch.
> https://jira.jboss.org/browse/JBRULES-2709
There was a small bug with this patch which broke during serialisation.
ObjectTypeConfs are not marshalled, thus the isTmsEnabled state was
being lost. It now re-determines that state during input marshalling.
Mark
>
> 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
>
>
> _______________________________________________
> 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/20101006/c5491b28/attachment-0001.html
More information about the rules-dev
mailing list