freenode/#lisp - IRC Chatlog
Search
6:03:29
beach
Lord_Nightmare: I do have a project to update the standard, but it is VERY modest compared to most suggestions I see here: https://github.com/robert-strandh/Well-Specified-Common-Lisp
6:05:06
Lord_Nightmare
my idea was more to 'mark the less useful leftovers which could probably be removed', since i understand the roots of common lisp are over 50 years old and a lot of people poured a lot of thought into it
6:06:18
beach
Lord_Nightmare: That would be one of the less useful modifications. People can just ignore them. They only pose problems to people implementing Common Lisp systems.
8:19:56
beach
muresanvlad_: Some people write applications that never allocate any memory. In that case the garbage collector is never alled.
8:23:48
trittweiler
muresanvlad_, In a C program, how often do you think malloc is called on average?
8:24:50
muresanvlad_
it's quite different. The GC can be called when you create a new variable,string or function
8:26:38
trittweiler
Doesn't it depend on the way the program is written? A C program doing a lot of text processing, would call malloc quite often, no?
8:27:19
muresanvlad_
right, I just wanted to know for an average small program how often the gc can be called once per second
8:28:25
loke
Major collections (the ones that take time) could be run every few minutes, even for large applciations. In some cases, several hours can pass.
8:29:24
loke
Usually, GC's split their heap into generations, since it has been shown that most memory gets collected almost instantaneously.
8:30:04
beach
muresanvlad_: There are small programs that don't allocate any memory, and there are others that allocate a lot. It is completely meaningless to talk about averages here.
8:30:07
loke
So memory gets allocated on the young generation, and after a while gets “promoted”. The old generation is only GC'ed when it fills up, which means that it can take quite some time becfore the majority of memory is ever GC'ed
8:31:54
loke
If you really want to, you can always look at the GC in a specific implementation (and its settings) and then write a program that directly targets theat particular GC implementation.
8:32:26
loke
Just like you can write programs that directly target the malloc implementation in a given operating system and trigger some naty behaviour (like fragmentation)
8:36:09
aeth
If you need to avoid the GC in part of your program or profile exactly where/when the allocations happen/etc., SBCL ime is the easiest for this.
8:37:43
aeth
Murii__: It's pretty easy to see exactly how much or how little the GC is called in SBCL
8:37:55
beach
Murii__: There is a very deep result in the GC literature which is that as the size of your heap increases compared to the working set of your application, the cost of garbage collection as a fraction of your application execution time goes to 0.
8:39:07
beach
Murii__: People also imagine that manual memory management like malloc()/free() is cheaper than tracing garbage collection. That is not true at all.
8:40:31
beach
Murii__: The amount of work that malloc()/free() have to do is definitely not negligible. Do you know how an implementation of those works?
8:41:33
aeth
Murii__: You can see a lot about what's going on in SBCL's GC with the stuff mentioned here (and its profiling stuff in general): http://www.sbcl.org/manual/#Garbage-Collection
8:41:47
beach
Murii__: I just implemented a version of Doug Lea's algorithm, and I studied Paul Wilson's excellent survey paper about memory allocators.
8:42:57
beach
Murii__: Again you are confused. The algorithms used by typical malloc()/free() implementations can be learned without writing a single line of C code. They general purpose allocator techniques that work in any language.
8:45:20
loke
I also have experience in the subject. More so than the average programmer at the very least. I think a lot of people on this channel know what they are talking about.
8:46:39
lieven
Murii__: go read up on the boehm-gc stuff for example. There are cases of existing C programs speeding up when linked with it. It basically replaces the stdlib's malloc/free pair with its own where free is a nop and does gc.
8:53:14
schweers`
beach: a garbage collecting system would not necessarily have anything directly resembling malloc, right?
8:54:00
loke
schweers: if you define malloc() as being “something that provides free memory to whomever requests it” then it must have. :-)
8:54:40
jackdaniel
ACTION waits for infinite-memory-systems, where no garbage needs to be freed or collected :-)
8:55:57
schweers`
Murii__: quite possible, I wanted to know if it must be this way for all garbage collectors. I assumed that this is not the case, and beach confirmed this.
8:56:00
loke
jackdaniel: Some application are written as such. I've seen very memory hugly Java applications running with the GC turned off. They just restart the application every night (effectively creating a single GC :-) )
8:56:34
schweers`
loke: my bias tells me that this is stupid. is there a legitimate reason for this?
8:57:07
loke
(they don't actually turn it off, but they set the heap size to a ridiculous size, and tune it so that it only GC's if it absolutely needs to, which is never)
8:57:12
beach
schweers`: A good Common Lisp system will have a "nursery", i.e. a generation of youngest objects from which new objects are allocated. And they use a copying collector, so that allocation is just a matter of testing and incrementing a pointer.
8:58:10
loke
schweers: well, they are essentially working around limitations in the software. As the customer dataset grew, they needed more and more heap. Once they git a heap size of around 50 GB or more, the full GC took so long that it blocked transactions in the system.
8:58:17
beach
schweers`: Whereas the standard implementation of malloc() has to look for a best-fit block among all free blocks in memory.
8:58:56
loke
beach: No need to even test the pointer. An allocation is literally just an ADD instruction.
8:59:10
schweers`
loke: my question may sound naive but ... why not have smaller collections on the way? As far as I know, the jvm has this as default behavior anyway, right?
8:59:21
loke
beach: You set of a readonly memory page after the free heap, and then you'll get a SEGV when you hit it, which can trigger a minor GC
9:00:55
loke
beach: That's the reason why you can't load the JVM into SBCL wusing FFI. Both of them tries to handle SEGV and they confuse eachother leading to a crash.
9:02:33
loke
it saves a conditional jump instruction (and perhaps a CMP, depending on how you lay things out in memory) per allocation. That adds up.
9:03:28
beach
I would think that cost would be swamped by the necessity of allocating memory in order to initialize the object allocated. Plus, the branch-prediction logic will guess the right thing almost all the time.
9:04:38
trittweiler
Posterdati, Might want to add a short section in the beginning what this is about. I didn't know what Prometheus.io is, and because the name of the library is essentially the same as that service, I didn't quite get it at first. (Usually, the convention used to be to call this thing cl-prometheus rather than prometheus.cl, but that's just names.)
9:04:47
loke
beach: I'm sure it's possible to avoid page table hackery, but how much you gain I don't know.
9:05:05
loke
The benefot of not doing it would be that you can easily link in the Java VM in the same process, which would be useful.
9:05:05
schweers`
it seems to me that low level languages like C have done so much optimization, that this way of handling memory and optimizing it is completely lost to them.
9:05:15
trittweiler
Posterdati, I find the numbers in the tables confusing too. Is it really N (operations) per second? In that case, the implementation via mutex wins?
9:05:43
beach
schweers`: They can't do better if they assume that objects won't move once allocated.
9:06:27
schweers`
Is moving objects not at least somewhat expensive? It seems so to me, but then again, I don’t know much about GC.
9:06:46
beach
schweers`: In my opinion, this is the reason for the complexity of C++. They made the decision from day 1 to use manual memory management.
9:08:36
schweers`
not to bash on Stroustroup, but it seems to me like C++ is a quick hack gone too far.
9:09:12
beach
Posterdati: Here is how I see it. Common Lisp and other modern languages enforce uniform reference semantics. That is impractical without GC. Without it, you must distinguish between objects and pointers to them and you must be very careful when counting references and/or copying objects. That is a large part of the complexity of C++.
9:10:01
schweers`
nah, I disagree with him on language design, but I can kind of see how this can happen. Also, he did a remarkable job, in a way. I couldn’t have done what he has. Also, it was a different time.
9:10:41
schweers`
well, maybe for some really weird niche platform. But I guess there are better languages today for any purpose.
9:12:50
trittweiler
beach: C++ tries really hard to make it possible to use the stack for allocations because allocating on the stack is cheap (it's just a pointer increment! - oh the irony)
9:15:41
schweers`
shka: I’m afraid I don’t recall any details, but I remembering thinking that some things in CL seemed weird and somewhat arbitrary, until I got how they work together. Then it just seemed (and seems) amazing.
9:16:00
Posterdati
well every languages has got its own purpose, I still don't catch the c++ purpose, I mean it is not for system programming, nor for AI, databases? Who knows...
9:16:27
aeth
trittweiler: CL has (declare (dynamic-extent foo)) for possible stack allocations. http://www.lispworks.com/documentation/HyperSpec/Body/d_dynami.htm
9:17:01
schweers`
Posterdati: it is sometimes used for embedded devices, as it has some features which make it a little more pleasant to use than C. Which says more about C than C++, if you ask me.
9:17:36
Posterdati
schweers: on Arduino is nice, but not desiderable, I use to program them using c...
9:18:32
aeth
C++ seems to be very popular in high performance and/or real-time programs, e.g. game engines.
9:19:11
schweers`
aeth: I wonder how much of this is just history, and how other languages (CL in particular) would fare in this domain
9:19:25
aeth
Pretty much every game engine is C++, even if they let you use a different language for the part you write (like Unity's C#)
9:20:12
aeth
schweers`: Well, as far as history goes, in the 1980s games were written mostly in asm, and portable games were written that way until probably 2004 or so. In the 1990s, games got to use C and about 15 years ago they switched to C++.
9:25:16
schweers`
But even if CL were not a good candidate for AAA games, I guess that other languages might. Rust maybe?
9:34:08
shka
schweers`: needlessly to say, currently you can simply grab unreal engine or unity engine and stick to it
9:34:42
aeth
schweers`: The big problem with writing a game engine in Common Lisp (or, really, anything that's not C++) is that you have to do everything yourself instead of using existing solutions.
9:35:00
_death
did you realy suggest a language created less than a decade ago and constantly changing for a huge codebase?
9:35:19
schweers`
I didn’t realize that there were so many libraries that game engine developers could use.
9:35:55
schweers`
_death: in case you meant me suggesting rust, it was just a wild idea. I’m not seriously suggesting it, no.
9:37:33
aeth
shka: Interfacing CL with Unity or Unreal? It may or may not be impossible, but it's probably a bad idea.
9:39:46
aeth
As for Rust: https://www.reddit.com/r/rust/comments/78bowa/hey_this_is_kyren_from_chucklefish_we_make_and/
9:44:47
_death
aeth: skimming it I did not see any indication of the code base size.. anyway, to me Rust is one of the most distasteful languages in use.. so I may be biased ;)
11:01:50
figurelisp
where did you guys learn dataq structures in lisp? Not the data structures implemented in lisp but to try to implement them.In a functional way
11:03:34
eminhi
Finally figured out, that the warning i got was due to defining test-system to run tests in test-op, not on load-op.
11:10:15
hajovonta
unfortunately sometimes I had to look up functions like append and such in the beginning
11:12:32
figurelisp
there are books that teach to implement data structures like trees, graphs in imperative programming languages like java,c++ and others adn there is also data structures books for haskell, ML. Are there no books like these for Common lisp?
11:16:22
LdBeth
figurelisp: if you have already read those books i think the only additional thing you have to do is learning CLOS, which gives you the ability to implement complex data structures in CL
11:25:14
beach
figurelisp: An implementation in Common Lisp of some data structure would use exactly the same elements as are used in other languages. Common Lisp has vectors, lists, and standard objects which provide those elements.
11:26:07
hajovonta
it's not really harder or easier to implement complex data structures in CL than in other languages
11:28:43
beach
figurelisp: Now, what do you mean by "In a functional way"? Do you mean that the data structure is persistent (in the sense that applying an operation to it generates a new instance and leaves the original one intact), or do you mean that you want to implement traditional data structures that can be mutated but you want to use a functional style for the implementation?
11:30:16
beach
figurelisp: If it is the former, then you just follow the literature on how such data structures are implemented. If it is the latter, then you are looking in the wrong direction, because Common Lisp is not a particularly "functional" language in that respect. You would rather use standard objects and generic functions in an imperative style.
11:33:58
beach
figurelisp: I am asking whether you are referring to the property of the data structure you want to implement, or to the programming style to do it.
11:35:08
figurelisp
like the basic dataq structures are implemented in haskell but they are functional
11:35:09
beach
figurelisp: You can do that in Common Lisp, but that's not the typical Common Lisp style.
11:36:01
figurelisp
I don't know much about functional programming so i am not certain how they are implemented. I was thinking to learn functional paradigm through CL
11:37:08
beach
figurelisp: What antoszka says. Common Lisp shines with its object system, its condition system, etc. Not for its support for functional programming.
11:37:34
antoszka
figurelisp: It doesn't force you into functional thinking (like Clojure/Haskell do), nor does it really provide any strictly functional facilities.
11:37:38
beach
But you can definitely use a functional style in Common Lisp. It is often done to implement macros for instance.
11:39:17
figurelisp
My main objective is to learn CL. Now i am reading CL:gentle introduction but after that i thought the next path would be to learn how to implement basic data strucutes. that's all what i want to achieve right now
11:40:06
beach
figurelisp: You would have simpler data structures and a more natural Common Lisp programming style.
11:41:42
figurelisp
so what you are saying is I should try to implement it on my own and then ask for help and code review here?
11:41:52
edgar-rft
figurelisp, there'a ton of builtin data structures you can use, we would need to know more details what you need exactly
11:42:43
beach
figurelisp: The stack is particularly simple for the very simple case, but I can show you situations where the simple case is inadequate.
11:43:44
beach
figurelisp: (defgeneric push (item stack)) (defgeneric pop (stack)) (defgeneric emptyp (stack))
11:44:42
figurelisp
beach: sorry to interrupt but i will not be abel to understand it right now. I'll complete the introdution book and then i'll learn from you
11:45:57
hajovonta
beach: oh come on. (defparameter stack nil) (push 1 stack) (push 2 stack) (pop stack):)
11:46:36
beach
hajovonta: That won't respect the most elementary restriction on an imperative data structure, namely that it has its own first-class identity.
11:47:51
beach
hajovonta: Try (defparameter stack2 stack1) then (push 234 stack1). For it to be moodular, stack2 must change as well. Otherwise, your implementation is showing in the interface which is unacceptable.
11:49:04
beach
hajovonta: The Common Lisp list is not an abstract data type. I call it a "concrete" one. So it can be used to implement an abstract data type, but it can't be used as such by itself.
11:53:50
beach
LdBeth: The array with a fill pointer has the problem that you can not guarantee, nor even come close to, O(1) complexity for the operations.
11:54:27
beach
LdBeth: The list version has the problem that if you want a stack of (say) DNA letters, then storing 2 bits costs you 126 bits overhead.
11:55:50
beach
LdBeth: So it is not a simple question of preferring one to the other. It has to do with conforming to specifications. In the case of a stack, I can eliminate both problems with a slightly more complicated implementation.
11:57:11
hajovonta
it would be interesting to create a closure-based implementation and see comparisons.
11:58:02
beach
hajovonta: That would be essentially the same as the one that uses a standard class above, except it would be less flexible.
11:58:17
beach
hajovonta: The closure would play the same role as the instance of the standard class.
12:20:09
LdBeth
beach: why array with fill pointer can’t guarantee O(1) complexity, except you mean when the stack is full and needs to be resized
12:24:48
hajovonta
beach: I would think, after reading let over lambda, that closures are more flexible than using objects.
13:18:46
pfdietz
Vectors with fill pointers can implement stacks in O(1) amortized time per operation.
13:20:02
pfdietz
This is fine unless you have real time constraints, or if you're trying to make the stack "fully persistent" (where updates can be done on past versions in a branching model of time.)
13:21:25
beach
pfdietz: Correct. I was referring to the worst-case complexity of one single operation.
13:22:21
pfdietz
It's possible to get to O(1) worst case time by a more clever approach, where the copying to the new larger vector is spread out over O(n) updates. This still doesn't help with full persistence though.
13:22:29
beach
hajovonta: You can't stick an auxiliary method that specialized according to the particular type of the closure.
13:23:06
pfdietz
Another lispy example of this is implementation of a queue with stacks. Using two stacks you can do queue ops in O(1) amortized time, but you can also do it in O(1) worst case time with some effort.
13:23:18
beach
pfdietz: The better solution that solves both problems is to use a list of constant-size vectors.
13:25:33
beach
pfdietz: Interestingly, when I came up with that solution, I checked it with the algorithms and data structures expert in the lab (I do not consider myself an expert, though I may have to rethink that), and he had never heard of it, nor had he ever contemplated the problems with the list or the vector solution (space vs real-time).
13:29:59
beach
pfdietz: Using a list to implement a stack has the problem that each element takes 2 words. So if you want a stack of bits or of DNA letters, you wast a lot of space.
13:30:47
beach
pfdietz: If you use a vector instead, you are sacrificing real-time behavior, so you can't propose it to gamers for instance. Occasionally an operation may take linear time.
13:31:28
beach
If you use a list of constant-size vectors, you can have vectors of bits, and provided the vector is big enough, you can make the 2 words waste arbitrarily small.
13:31:52
Zhivago
Gamers don't really care about real-time -- they just care about latency spikes. In practice they just make things excessively fast enough that the spikes they do get are acceptable.
13:31:56
pfdietz
There's a theme in data structure design where you layer two different kinds of data structures, using a different one for small chunks. This looks like an example of that.
13:32:10
beach
pfdietz: Furthermore, you only ever need to allocate a constant-size vector and you never need to move more than that many objects, so you have constant time operations.
13:33:10
pfdietz
And the overhead of the links can be spread over the length of the vectors, and so can be made as small as desired.
13:33:56
Zhivago
I think you'll find that gamers are happy with the terrible things that STL does to extensible vectors in most cases. :)
13:34:30
pfdietz
Where I was not clear was that you were reducing the space overhead, minimizing the constant.
13:34:54
beach
Zhivago: I actually don't care much about that particular use case. I chose the wrong example. Again, I'm sorry.
13:36:22
shka
anyway, it you can have hard real time behavior as a component in system that is supposed to have soft real time characteristics without drawback, you potentially can save yourself headache when optimizing
13:47:45
beach
pjb: Clearly, for the side-effect-free version of the stack, the vector solution is totally out. The list of constant-size vectors might still be acceptable.
13:49:02
beach
pjb: If you have very small objects, like bits or DNA letters, you can copy the entire thing very efficiently, so you are no worse off than with a pure list.
13:49:21
beach
pjb: And if you have large objects, you converge toward the pure list solution anyway.
13:51:02
pjb
This is why we have programmers: there are always special circumstances that require specific data structures and algorithms.
14:34:35
flip214
would it be too much to ask that "Beta" gets removed from the documentation pages, eg. https://www.quicklisp.org/beta/releases.html (URL and text)?
14:48:01
JuanDaugherty
so the problem I was having with mcclim demo was due to trying to run under vnc
14:56:45
Bike
somewhat to my surprise, you can pass any input stream to LOAD, as far as i can tell. but if you do, and the stream has no associated file, i'm not sure what *load-truename* and *load-pathname* ought to be bound to. anyone know?
15:01:43
Bike
I mean, for example, in (with-input-from-string (s ("print *load-pathname*)") (load s)), what is printed.
15:02:50
beach
Bike: Good question. I don't see the answer to it anywhere. Something for WSCL to specify, it seems.
15:23:40
beach
figurelisp: I am a researcher and I have chosen Common Lisp both as my research project and as a vehicle to accomplish it.
15:24:30
beach
It's because where I work, we don't have the pressure they have in some countries to get grants, etc. So I can choose what I do.
15:39:52
LdBeth
Basically I learned Lisp because I’m not required to learn any particular PL and out of mania on retro computing
15:45:23
LdBeth
Actually CLtL2 is written before I was born. So I consider it as retro. Plz forgive me if that annoys you
15:51:49
LdBeth
Just because it’s strong typed. In untyped lambda calculus even Y combinator can be applied to an int
17:40:27
flip214
https://github.com/pcostanza/closer-mop says "This page is taking way too long to load."