[George] another question on struct behaviour.

[pixelfck]

I have some further questions on the intersting workings of structs:

1
How does the efficiency (in clock cycles) of assigning a value to a (previously defined) struct label compare to assigning a value to a regular (previously defined) variable?

and

How does the efficiency compare for retrieving a value from a variable to retrieving a struct value using the (@ foo 'bar) syntax?

2
Struct can be made to recursively point to each other:

Code: Select all

(block (verticles edges)
	(setq verticles
		{i: 0 edge: Nil}
		{i: 1 edge: Nil}
		{i: 2 edge: Nil}
		{i: 3 edge: Nil}
		)
	
	(setq edges
		{n: 0 from: (item verticles 0) to:  (item verticles 1)}
		{n: 0 from: (item verticles 1) to:  (item verticles 2)}
		)
	
	(set@ (item verticles 0) 'edge (item edges 0))
	)

• Is this recursion supported by the engine?
• To what extent?
• Is there any negative impact on memory usage and/or performance?

(I'm implementing Davidson and Harel's Simulated Annealing method for drawing graphs nicely and since it is rather inefficient, I would like to not waste any clock cycles if possible)

[george moromisato]

1. I haven't tested it, but I suspect that variable access will be maybe three or four times faster than struct field access. In the case of variable, the engine caches the value of the variable, but for structs we have to do a lookup (log n, unfortunately). You might be better off with lists. An index into a list is linear (minus some setup time for caching):

Code: Select all

(@ someList 4) -> linear time
(@ someStruct 'someKey) -> log n (where n is the number of keys in someStruct).

2. Unfortunately, recursive pointers like you propose will leak memory in the current engine. I use a ref-counted system of memory management instead of garbage collection. The only way to prevent the memory leak would be to break the links (by setting to Nil) before letting the variable go out of scope.

3. The paper you point to looks fascinating. Are you trying to build a random gate network? If so, please keep me up to date on your progress. It sounds like a generally useful idea.

Your best bet might be to use lists of integers as indices into other lists (instead of pointers). For example, imagine the following implementation:

Code: Select all

(setq vertexList
   (list
      (list 0 0 Nil)   ; The 0th vertex at position 0,0 (we'll fill in the Nil with a list of edges later)
      (list 5 0 Nil)   ; The 1st vertex at position 5,0
      (list 0 5 Nil)   ; The 2nd vertex at position 0,5
      )
   )

(setq edgesList
   (list
      (list 0 1)     ; An edge from vertex 0 to 1
      (list 1 2)     ; An edge from vertex 1 to 2
      (list 2 0)     ; An edge from vertex 2 to 0
      )
   )

; Vertex 0 has two edges, 0 and 2 (these are indices into the edgesList list)
(set@ (@ vertexList 0) 2 (list 0 2))

; Vertex 1 has two edges, 0 and 1
(set@ (@ vertexList 1) 2 (list 0 1))

; Vertex 2 has two edges, 1 and 2
(set@ (@ vertexList 2) 2 (list 1 2))

[pixelfck]

Thanks for the response.

I think I will indeed go with the lists and index option, it will off-course not result in the most readable code, but I think the linear performance is worth it.

And yes, you guessed correctly in that I'm building a randomly (rule-based) generated gate network. The biggest issue is to position the node in the resulting network in such a way that it 'makes sense' to the human eye.
I've the a working implementation of the Fruchterman Reingold force directed algorithm but resulting layout usually has too many edge crossings to my taste.

Cheers,
Pixelfck