April 2016 - Pharo-dev - lists.pharo.org

Re: [Pharo-dev] Class allSubInstances size takes 23 seconds to run on Pharo 5 on OS X

by Bernhard Pieber

Wow, thanks for the detailed explanation! Cheers, Bernhard > Am 21.04.2016 um 16:48 schrieb Eliot Miranda <eliot.miranda(a)gmail.com>: > > Hi Bernhard, > >> On Apr 20, 2016, at 9:56 PM, Bernhard Pieber <bernhard(a)pieber.com> wrote: >> >> Hi Eliot, >> >> Right, but in the latest Squeak5.1-trunk with the latest CogSpur.r3663.app it takes only 3 milliseconds. I guess itâs just an optimized implementation, there. (Canât look right now.) > > Indeed ;-). In most Smalltalk implementations an object's header contains a direct reference (a pointer) to its class, but in Spur, an object's header contains a "class index" (as does the Dart VM). IIRC this is an approach first tried in a system at Xerox PARC, but what follows, I invented for 64-bit VW, to avoid having 64-bits of class reference in every object. > > The object header contains both a 22-bit classIndex, for up to 4 million classes, and a 22-bit identityHash field for 4 million hash values. The classIndex is used in all method caches, which has advantages for the GC, and means that when sending a message via an inline cache, the object's index is fetched, not its class. > > Classes are stored in a hidden two-level sparse array (array of arrays), the class table. If the object's class object is required (for the #class message or to do a full message lookup searching the inheritance hierarchy) the classIndex is used to index the class table. > > The classes known to the VM, Array, Message, Context, LargeNegativeInteger, LargePositiveInteger have known indices and occupy the first page of the class table. So the VM can allocate instances of these by simply writing a header containing the relevant classIndex. A conventional implementation would have to fetch the class from the specialObjectsArray and write it into the header (and in pre-Spur, there are 31 "compact class indices" of which a handful are used for a subset of the classes). > > But how does the VM find the classIndex of an arbitrary class? Searching the table would be very slow. So Spur arranges that a class's identityHash is also its index in the classTable. Classes have their own special identityHash primitive, see Behavior>>#identityHash. Whenever the VM tries to Instantiate a class, or whenever the class's identityHash primitive is run, if the class's identityHash is zero, the VM assigns an unused index in the class table as the identityHash and stores the class in the table. So a class's identityHash is its index in the class table. > > To Instantiate a class its identityHash is copied into the classIndex field of the new instance's header. To search for all instances of a class, the VM searches for objects whose classIndex is that class's identityHash. A consequence is that if a class doesn't yet have an identityHash (identityHash = 0) it can't have instances, and so there is no need to scan the heap. > > > Note that you can't (easily) tell from the image. If you send identityHash to a class that will enter it into the table. There's a hidden hasIdentityHash primitive that can be used, and if you're curious I can post code to get at it. Note that this implies all the metaclasses are in the table because they have as their single instance a normal named class, but Metaclasses holds onto its instance via thisClass and so can also avoid traversing the heap. > > Some things to try: > > {Array. ByteString. Character. Context. LargeNegativeInteger. LargePositiveInteger. Message. SmallFloat64. BoxedFloat64. SmallInteger} collect: #identityHash > > and in a pre-Spur system > > Smalltalk compactClassesArray select: [:c| Smalltalk specialObjectsArray includes: c] thenCollect: [:c| {c. c indexIfCompact] > > Hope this explains what's going on under the covers. > >> Cheers, >> Bernhard >> >>> Am 20.04.2016 um 17:43 schrieb Eliot Miranda <eliot.miranda(a)gmail.com>: >>> >>> Hi Bernhard, >>> >>> >>>> On Apr 20, 2016, at 5:26 AM, Bernhard Pieber <bernhard(a)pieber.com> wrote: >>>> >>>> Dear Pharoers, >>>> >>>> I found something strange: >>>> Time millisecondsToRun: [ Class allSubInstances size ]. â23617" >>> >>> Because it does an allInstances for Class and all its subclasses, and allInstances visits every object in the heap, so this does thousands of scans of the heap. >>> >>> >>>> I did this on a new Pharo 5 image >>>> curl get.pharo.org/alpha+vmLatest | bash >>>> >>>> Can somebody confirm this on their machine? What might be the reason? >>>> >>>> Cheers, >>>> Bernhard >> >> >

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by Robert Withers

Hi CÃ©drik, Have you considered seeing if there are any Voronoi diagram packages in one of the repositories? I believe there is a fair bit of research into algorithms. You search use of spaciotemporal collated data sounds very interesting and there is a segment on computation over segments in this slide deck, that might be something, I don't know: http://graphics.stanford.edu/courses/cs368-06-spring/handouts/Delaunay_2.pdf. Certainly there is utility on the graphics side to use a 4D quadratic model (with GPU accel) and may well be modeled already in squeak/Pharo. Would't that be something! Regards, Robert On 04/23/2016 01:29 PM, CÃ©drick BÃ©ler wrote: > Hi Esteban, > > Thanks a lot, I think Iâll try your History package, it seems to be a very good starting point (instead of hacking it myself). > Iâll try it soon. > > Thanks for all the information ;) > > Cheers, > > CÃ©drik > > >> Le 23 avr. 2016 Ã 18:28, Esteban A. Maringolo <emaringolo(a)gmail.com> a Ã©crit : >> >> Maybe instead of having a Dictionary, you can use my History package [1]. >> It allows you to add elements to "the history", and the History class >> will provide certain "lookup" strategies depending on how you want to >> query it. >> >> It is a trimmed down version of an utility class I used for years in >> commercial products where the History contained thousands of elements. >> This version uses linear search, my previous implementation used >> binary search which was significantly faster with lots of elements in >> the collection. >> >> Of course it doesn't solve your spatial queries needs, I don't know if >> there is something in Smalltalk for that other than the distance >> between two coordinates[2], PostgreSQL 9.2 has some support for >> "temporal" data/tables which you could combine with PostGIS if you >> need to combine a spatial query with a temporal one [3]. >> >> Regards, >> >> [1] http://www.smalltalkhub.com/#!/~emaringolo/History >> [2] http://pastebin.com/ThKDXCKK >> [3] http://clarkdave.net/2015/02/historical-records-with-postgresql-and-tempora… >> Esteban A. Maringolo >> >> >> 2016-04-23 12:13 GMT-03:00 CÃ©drick BÃ©ler <cdrick65(a)gmail.com>: >>> >>> Sure, but 1) that's not a lot >>> >>> 2) do you even know if you need interactive stuff or if batch processing is >>> ok? >>> >>> >>> interactive I would sayâ¦ but hard to be certain right now as it depends on >>> design choicesâ¦ do we cache ? do we aggregate past data ? extra indexes ? >>> Iâll see later. >>> I want something simple, keep everythingâ¦ and query according to time >>> interval, areas (contexts)â¦ >>> >>> But yes for now this is pointless to look for something optimal and Iâll use >>> a dictionary as it will be small at start. >>> >>> Cheers, >>> >>> CÃ©drik >>> >>> >>> >>> >>> -- >>> Damien Pollet >>> type less, do more [ | ] http://people.untyped.org/damien.pollet >>> >>> > -- Robert . .. ... ^,^

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by Alistair Grant

On Sat, Apr 23, 2016 at 02:13:22PM +0200, CÃ©drick BÃ©ler wrote: > Hi Alistair, > > Thanks, this sounds like a nice suggestion. > > I have to think about it. > Adding altitude would be also interesting in some cases but not as a start > (quite limited usage). > > When you say to package it separately, youâre talking about Geolocation, > Spatiotemporal classes ? or also the collection ? My impression was that the Geolocation & Spatiotemperal classes already exist (and presumably are already packaged), so I was thinking of the collection class (which would have the geolocation and spatiotemperal as dependencies). > I can try something but I think this will deserve more Â« computational > thinking Â» power than I have ^^ Me too, but having something is still better than nothing, and maybe someone will provide ideas for improvements. Cheers, Alistair

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by CÃ©drick BÃ©ler

Hi Esteban, Thanks a lot, I think Iâll try your History package, it seems to be a very good starting point (instead of hacking it myself). Iâll try it soon. Thanks for all the information ;) Cheers, CÃ©drik > Le 23 avr. 2016 Ã 18:28, Esteban A. Maringolo <emaringolo(a)gmail.com> a Ã©crit : > > Maybe instead of having a Dictionary, you can use my History package [1]. > It allows you to add elements to "the history", and the History class > will provide certain "lookup" strategies depending on how you want to > query it. > > It is a trimmed down version of an utility class I used for years in > commercial products where the History contained thousands of elements. > This version uses linear search, my previous implementation used > binary search which was significantly faster with lots of elements in > the collection. > > Of course it doesn't solve your spatial queries needs, I don't know if > there is something in Smalltalk for that other than the distance > between two coordinates[2], PostgreSQL 9.2 has some support for > "temporal" data/tables which you could combine with PostGIS if you > need to combine a spatial query with a temporal one [3]. > > Regards, > > [1] http://www.smalltalkhub.com/#!/~emaringolo/History > [2] http://pastebin.com/ThKDXCKK > [3] http://clarkdave.net/2015/02/historical-records-with-postgresql-and-tempora… > Esteban A. Maringolo > > > 2016-04-23 12:13 GMT-03:00 CÃ©drick BÃ©ler <cdrick65(a)gmail.com>: >> >> >> Sure, but 1) that's not a lot >> >> 2) do you even know if you need interactive stuff or if batch processing is >> ok? >> >> >> interactive I would sayâ¦ but hard to be certain right now as it depends on >> design choicesâ¦ do we cache ? do we aggregate past data ? extra indexes ? >> Iâll see later. >> I want something simple, keep everythingâ¦ and query according to time >> interval, areas (contexts)â¦ >> >> But yes for now this is pointless to look for something optimal and Iâll use >> a dictionary as it will be small at start. >> >> Cheers, >> >> CÃ©drik >> >> >> >> >> -- >> Damien Pollet >> type less, do more [ | ] http://people.untyped.org/damien.pollet >> >> >

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by Esteban A. Maringolo

Maybe instead of having a Dictionary, you can use my History package [1]. It allows you to add elements to "the history", and the History class will provide certain "lookup" strategies depending on how you want to query it. It is a trimmed down version of an utility class I used for years in commercial products where the History contained thousands of elements. This version uses linear search, my previous implementation used binary search which was significantly faster with lots of elements in the collection. Of course it doesn't solve your spatial queries needs, I don't know if there is something in Smalltalk for that other than the distance between two coordinates[2], PostgreSQL 9.2 has some support for "temporal" data/tables which you could combine with PostGIS if you need to combine a spatial query with a temporal one [3]. Regards, [1] http://www.smalltalkhub.com/#!/~emaringolo/History [2] http://pastebin.com/ThKDXCKK [3] http://clarkdave.net/2015/02/historical-records-with-postgresql-and-tempora… Esteban A. Maringolo 2016-04-23 12:13 GMT-03:00 CÃ©drick BÃ©ler <cdrick65(a)gmail.com>: > > > Sure, but 1) that's not a lot > > 2) do you even know if you need interactive stuff or if batch processing is > ok? > > > interactive I would sayâ¦ but hard to be certain right now as it depends on > design choicesâ¦ do we cache ? do we aggregate past data ? extra indexes ? > Iâll see later. > I want something simple, keep everythingâ¦ and query according to time > interval, areas (contexts)â¦ > > But yes for now this is pointless to look for something optimal and Iâll use > a dictionary as it will be small at start. > > Cheers, > > CÃ©drik > > > > > -- > Damien Pollet > type less, do more [ | ] http://people.untyped.org/damien.pollet > >

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by CÃ©drick BÃ©ler

> > Sure, but 1) that's not a lot > 2) do you even know if you need interactive stuff or if batch processing is ok? interactive I would sayâ¦ but hard to be certain right now as it depends on design choicesâ¦ do we cache ? do we aggregate past data ? extra indexes ? Iâll see later. I want something simple, keep everythingâ¦ and query according to time interval, areas (contexts)â¦ But yes for now this is pointless to look for something optimal and Iâll use a dictionary as it will be small at start. Cheers, CÃ©drik > > > > -- > Damien Pollet > type less, do more [ | ] http://people.untyped.org/damien.pollet <http://people.untyped.org/damien.pollet>

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by Damien Pollet

On 23 April 2016 at 16:04, CÃ©drick BÃ©ler <cdrick65(a)gmail.com> wrote: > 1000 per day in 100 years => 36 500 000 > > What I want is keeping track of all positions a person can have in his > life (what can easily reach millions) and then rely on these Â« points Â» to > index information added in the system. > Sure, but 1) that's not a lot 2) do you even know if you need interactive stuff or if batch processing is ok? -- Damien Pollet type less, do more [ | ] http://people.untyped.org/damien.pollet

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by CÃ©drick BÃ©ler

> > Hi Cedrick, welcome back in the community. Thanks, I was not very far though ^^ > >> For a project Iâm starting to prototype, I need collections where objects are inserted according to an index that is a spatiotemporal object. >> >> The idea is that each time a person add an Â« information" in this collection, he does it a a given place and time and I want to be able to query the collection easily according to place or time (or both). >> >> Iâm hacking it right now but I wonder if people have ideas on that subject. Iâm also interested in collection that that are indexed by the timestamp of the insertion. >> >> For the implementation of spatiotemporal classe, I choose to use a ZTimestamp and a Geolocation object. Geolocation is quite simple and is responsible among other to get the timezone, but of courses coordinates (or eventually areas). >> >> For the collection, Iâm still wanderingâ¦ Something like an OrderedCollection with another internal array to store associated spatiotemporal(s)â¦ Will hack something but Iâd love to hear others ideas. > > You mean something like a timeseries ? > I start to work on a basic TimeSeries class quite similar to the one > you find in Panda: > http://pandas.pydata.org/pandas-docs/stable/timeseries.html <http://pandas.pydata.org/pandas-docs/stable/timeseries.html> I donât really know, more a geospatial timeserie but It might be interesting. Weâll exchange on that subject I guess. Cheers, CÃ©drik > > -- > Serge Stinckwich > UCBN & UMI UMMISCO 209 (IRD/UPMC) > Every DSL ends up being Smalltalk > http://www.doesnotunderstand.org/ >

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by CÃ©drick BÃ©ler

> > There are a lot of spatial access data structures: https://en.wikipedia.org/wiki/Spatial_database#Spatial_index <https://en.wikipedia.org/wiki/Spatial_database#Spatial_index> > > But for a prototype I don't think you care; a simple linear search should be ok for testing Yes sure but I keep that in mind for later Â« exploration Â». > until you have thousands and thousands of records. Potentially, on a person lifetime, adding hundreds information a day (and probably higher order of magnitude), I think we can easily reach millions of data quite easily :) 100 per day, in 10 years => 365 000 1000 per day in 100 years => 36 500 000 What I want is keeping track of all positions a person can have in his life (what can easily reach millions) and then rely on these Â« points Â» to index information added in the system. > It's probably more important to really explore what you need and how your constraints will influence the API but I agree and Iâll work on that first. > (e.g. since we haven't invented teleportation yet, events for one person that are close in time are necessarily close in space) yesâ¦ for now but in 50 years who knows :) This remark is nevertheless interesting as a premise that can be used to check the validity of data (geospatial resolver are not that precise). But yeah for now, an OrderedDic or another classic collection will do the job and will let me explore the API (and we might discuss it ^^). I start this discussion as I thing this is one central modeling concept of what I want to do. Cheers, CÃ©drik > > On 23 April 2016 at 14:08, CÃ©drick BÃ©ler <cdrick65(a)gmail.com <mailto:cdrick65@gmail.com>> wrote: > Thanks Max, > > Iâve seen in Pharo 5 OrderedDictionary, OrderedPreservingDictionary and some others. I guess they have the same intent. > > I was actually trying them right now :) > > Cheers, > > CÃ©drik > > > > > Le 23 avr. 2016 Ã 13:57, Max Leske <maxleske(a)gmail.com <mailto:maxleske@gmail.com>> a Ã©crit : > > > > There was talk about an ordered dictionary implementation IIRC a couple of months ago on this list. > > > > Iâve attached an implementation I found in a thread from 2010 (may not work out of the box). > > > > Cheers, > > Max > > > > > > <OrderedDictionary.st> > > > >> On 23 Apr 2016, at 13:46, CÃ©drick BÃ©ler <cdrick65(a)gmail.com <mailto:cdrick65@gmail.com>> wrote: > >> > >> A dictionary with keys being the timestamp or the spatiotemporal object would probably do it... > >> I think Iâll do that but I wonder if there are better solutions out there ^^. > >> > >> Cheers, > >> > >> CÃ©drik > > > > > > > > -- > Damien Pollet > type less, do more [ | ] http://people.untyped.org/damien.pollet <http://people.untyped.org/damien.pollet>

April 23, 2016

Re: [Pharo-dev] Collection with spatiotemporal indexation - Ideas and discussions ?

by Serge Stinckwich

On Sat, Apr 23, 2016 at 6:39 PM, CÃ©drick BÃ©ler <cdrick65(a)gmail.com> wrote: > Hi Pharoers, Hi Cedrick, welcome back in the community. > For a project Iâm starting to prototype, I need collections where objects are inserted according to an index that is a spatiotemporal object. > > The idea is that each time a person add an Â« information" in this collection, he does it a a given place and time and I want to be able to query the collection easily according to place or time (or both). > > Iâm hacking it right now but I wonder if people have ideas on that subject. Iâm also interested in collection that that are indexed by the timestamp of the insertion. > > For the implementation of spatiotemporal classe, I choose to use a ZTimestamp and a Geolocation object. Geolocation is quite simple and is responsible among other to get the timezone, but of courses coordinates (or eventually areas). > > For the collection, Iâm still wanderingâ¦ Something like an OrderedCollection with another internal array to store associated spatiotemporal(s)â¦ Will hack something but Iâd love to hear others ideas. You mean something like a timeseries ? I start to work on a basic TimeSeries class quite similar to the one you find in Panda: http://pandas.pydata.org/pandas-docs/stable/timeseries.html -- Serge Stinckwich UCBN & UMI UMMISCO 209 (IRD/UPMC) Every DSL ends up being Smalltalk http://www.doesnotunderstand.org/

April 23, 2016